Denis Efimov

Johannes Schiffer

Romeo Ortega

Robustness of delayed multistable systems with application to droop-controlled inverter-based microgrids

Motivated by the problem of phase-locking in droop-controlled inverter-based microgrids with delays, the recently developed theory of input-to-state stability (ISS) for multistable systems is extended to the case of multistable systems with delayed dynamics. Sufficient conditions for ISS of delayed systems are presented using Lyapunov-Razumikhin functions. It is shown that ISS multistable systems are robust with respect to delays in a feedback. The derived theory is applied to two examples. First, the ISS property is established for the model of a nonlinear pendulum and delay-dependent robustness conditions are derived. Second, it is shown that, under certain assumptions, the problem of phase-locking analysis in droop-controlled inverter-based microgrids with delays can be reduced to the stability investigation of the nonlinear pendulum. For this case, corresponding delay-dependent conditions for asymptotic phase-locking are given.

I. INTRODUCTION

The increasing penetration of renewable distributed generation (DG) units at the low and medium voltage levels has a strong impact on the power system structure [START_REF] Farhangi | The path of the smart grid[END_REF], [START_REF] Pravin | Smart operation of smart grid: Risk-limiting dispatch[END_REF], [START_REF] Fang | Smart grid -the new and improved power grid: a survey[END_REF]. This fact requires new control and operation strategies to ensure a reliable and efficient electrical power supply [START_REF] Farhangi | The path of the smart grid[END_REF], [START_REF] Green | Control of inverter-based micro-grids[END_REF]. An emerging concept to address these challenges is the microgrid [START_REF] Lasseter | Microgrids[END_REF], [19], [START_REF] Farhangi | The path of the smart grid[END_REF]. A microgrid is a locally controllable subset of a larger electrical network. It is composed of several DG units, storage devices and loads.

Typically, most DG units in an AC microgrid are connected to the network via AC inverters [START_REF] Green | Control of inverter-based micro-grids[END_REF]. Under ideal conditions, an inverter-based DG unit can be modeled as an ideal controllable voltage source [START_REF] Lopes | Defining control strategies for microgrids islanded operation[END_REF], [START_REF] Rocabert | Control of power converters in AC microgrids[END_REF]. Furthermore, a popular control scheme to operate inverter-based DG units with the purpose to achieve frequency synchronization and power sharing in the network is droop control [START_REF] Chandorkar | Control of parallel connected inverters in stand-alone AC supply systems[END_REF], [START_REF] Guerrero | Advanced control architectures for intelligent microgrids -part I: Decentralized and hierarchical control[END_REF]. Conditions for stability in droop-controlled microgrids with inverters modeled as ideal controllable voltage sources have been derived, e.g., in [START_REF] Simpson-Porco | Synchronization and power sharing for droop-controlled inverters in islanded microgrids[END_REF], [START_REF] Schiffer | Conditions for stability of droop-controlled inverter-based microgrids[END_REF], [START_REF] Münz | Region of attraction of power systems[END_REF].

In general, inverter-based microgrids operated with droop control have several equilibria [START_REF] Simpson-Porco | Synchronization and power sharing for droop-controlled inverters in islanded microgrids[END_REF], [START_REF] Schiffer | Conditions for stability of droop-controlled inverter-based microgrids[END_REF]. Thus they are multistable systems. Stability analysis [START_REF] Angeli | Detection of multistability, bifurcations and hysteresis in a large class of biological positive-feedback systems[END_REF], [START_REF] Efimov | Oscillatority of nonlinear systems with static feedback[END_REF], [START_REF] Van Handel | Almost global stochastic stability[END_REF], [START_REF] Monzón | Local and global aspects of almost global stability[END_REF], [START_REF] Nitecki | Filtrations, decompositions, and explosions[END_REF], [START_REF] Rajaram | Connection between almost everywhere stability of an ODE and advection PDE[END_REF], [START_REF] Rantzer | A dual to Lyapunov's stability theorem[END_REF], [START_REF] Rumyantsev | Stability and stabilization of motion with respect to part of variables[END_REF], [START_REF] Smale | Differentiable dynamical systems[END_REF] and robust stability analysis [START_REF] Angeli | An almost global notion of input-to-state stability[END_REF], [START_REF] Angeli | Characterizations of input-to-state stability for systems with multiple invariant sets[END_REF], [START_REF] Angeli | Stability robustness in the presence of exponentially unstable isolated equilibria[END_REF], [START_REF] Chaves | Bistable biological systems: A characterization through local compact input-to-state stability[END_REF], [START_REF] Stan | Analysis of interconnected oscillators by dissipativity theory[END_REF] for this class of systems is rather complicated. Recently, the ISS theory [START_REF] Sontag | On the input-to-state stability property[END_REF] has been extended to multistable systems in [START_REF] Angeli | On input-to-state stability with respect to decomposable invariant sets[END_REF], [START_REF] Angeli | Characterizations of input-to-state stability for systems with multiple invariant sets[END_REF] (see also [START_REF] Christopher | Input-to-state stability, integral input-to-state stability, and unbounded level sets[END_REF] for discussion on ISS property with respect to an unbounded set).

Furthermore, in a practical setup, the droop control scheme is applied to an inverter by means of digital discrete time control.

Besides clock drifts, see, e.g. [START_REF] Schiffer | Droop-controlled inverters are robust to clock drifts[END_REF], digital control usually introduces time delays [START_REF] Kukrer | Discrete-time current control of voltage-fed three-phase PWM inverters[END_REF], [START_REF] Maksimovic | Small-signal discrete-time modeling of digitally controlled PWM converters[END_REF], [START_REF] Nussbaumer | Comparison of prediction techniques to compensate time delays caused by digital control of a three-phase buck-type PWM rectifier system[END_REF]. According to [START_REF] Nussbaumer | Comparison of prediction techniques to compensate time delays caused by digital control of a three-phase buck-type PWM rectifier system[END_REF], the main reasons for this are 1) sampling of control variables, 2) calculation time of the digital controller and 3) generation of the pulse-width modulation. We refer the reader to, e.g. [START_REF] Nussbaumer | Comparison of prediction techniques to compensate time delays caused by digital control of a three-phase buck-type PWM rectifier system[END_REF] for further details. To the best of the authors' knowledge this fact has yet not been considered in previous analysis of droop-controlled microgrids. Motivated by the abovementioned phenomenon, the main theoretical contribution of the present paper is to extend the recently derived ISS framework for multistable systems [START_REF] Angeli | On input-to-state stability with respect to decomposable invariant sets[END_REF], [START_REF] Angeli | Characterizations of input-to-state stability for systems with multiple invariant sets[END_REF] to multistable systems with delay (some preliminary consideration has Denis Efimov is with with Non-A team @ Inria, Parc Scientifique de la Haute Borne, [START_REF] Sontag | New characterizations of input-to-state stability[END_REF] been performed by the authors in [START_REF] Efimov | ISS of multistable systems with delays: application to droop-controlled inverter-based microgrids[END_REF]). In particular, sufficient conditions for ISS of multistable systems in the presence of delays are given in terms of a Lyapunov-Razumikhin function. It is also shown that ISS multistable systems are robust with respect to feedback delays. This result is illustrated via the example of a nonlinear pendulum. We would like to point out that related works on ISS of time-delay systems by employing Lyapunov functions [START_REF] Dashkovskiy | Lyapunov-Razumikhin and Lyapunov-Krasovskii theorems for interconnected ISS time-delay systems[END_REF], [START_REF] Fridman | Tutorial on Lyapunov-based methods for time-delay systems[END_REF], [START_REF] Pepe | On the Liapunov-Krasovskii methodology for the ISS of systems described by coupled delay differential and difference equations[END_REF] is limited to systems with a single equilibrium point or a compact attracting set. Next, based on the established results, we provide the main practical contribution: a condition for asymptotic phase-locking in a microgrid composed of two droop-controlled inverters with delay.

The analysis is conducted for a simplified inverter model derived under the assumptions of constant voltage amplitudes and ideal clocks, as well as negligible dynamics of the internal inverter filter and controllers. In that scenario, the delay merely affects the phase angle of the inverter output voltage. The stability results are illustrated by simulations.

II. PRELIMINARIES

For an n-dimensional C 2 connected and orientable Riemannian manifold M without a boundary, let the map f (x, d) :

M × R m → T x M be of class C 1 ,
and consider a nonlinear system of the following form:

ẋ(t) = f (x(t), d(t)), (1)
where the state x ∈ M and d(t) ∈ R m (the input d(•) is a locally essentially bounded and measurable signal) for t ≥ 0. We denote by X(t, x 0 ; d) the uniquely defined solution of (1) at time t fulfilling X(0, x 0 ; d) = x 0 . Together with (1) we will analyze its unperturbed version:

ẋ(t) = f (x(t), 0). (2)
A set S ⊂ M is invariant for the unperturbed system (2) if X(t, x; 0) ∈ S for all t ∈ R and for all x ∈ S. Define the distance from a point x ∈ M to the set S ⊂ M as |x| S = min a∈S δ(x, a), where the symbol δ(x 1 , x 2 ) denotes the Riemannian distance between x 1 and x 2 in M , |x| = |x| {0} for x ∈ M or a usual euclidean norm of a vector x ∈ R n . For a signal d : R → R m the essential supremum norm is defined as d ∞ = ess sup t≥0 |d(t)|.

A. Decomposable sets

Let Λ ⊂ M be a compact invariant set for (2).

Definition 1. [27]

A decomposition of Λ is a finite and disjoint family of compact invariant sets Λ 1 , . . . , Λ k such that

Λ = k i=1 Λ i .
For an invariant set Λ, its attracting and repulsing subsets are defined as follows:

A(Λ) = {x ∈ M : |X(t, x, 0)| Λ → 0 as t → +∞}, R(Λ) = {x ∈ M : |X(t, x, 0)| Λ → 0 as t → -∞}. Define a relation on W ⊂ M and D ⊂ M by W ≺ D if A(W) ∩ R(D) = .
Definition 2.

[27] Let Λ 1 , . . . , Λ k be a decomposition of Λ, then

1. An r-cycle (r ≥ 2) is an ordered r-tuple of distinct indices i 1 , . . . , i r such that Λ i1 ≺ . . . ≺ Λ ir ≺ Λ i1 . 2. A 1-cycle is an index i such that [R(Λ i ) ∩ A(Λ i )] -Λ i = .
3. A filtration ordering is a numbering of the Λ i so that Λ i ≺ Λ j ⇒ i ≤ j.

As we can conclude from Definition 2, existence of an r-cycle with r ≥ 2 is equivalent to existence of a heteroclinic cycle for (2) [START_REF] Guckenheimer | Structurally stable heteroclinic cycles[END_REF]. Furthermore, existence of a 1-cycle implies existence of a homoclinic cycle for (2) [START_REF] Guckenheimer | Structurally stable heteroclinic cycles[END_REF].

Definition 3. The set W is called decomposable if it admits a finite decomposition without cycles, W = k i=1 W i , for some non-empty disjoint compact sets W i , which form a filtration ordering of W, as detailed in definitions 1 and 2.

B. Robustness notions

The following robustness notions for systems represented by [START_REF] Angeli | An almost global notion of input-to-state stability[END_REF] have been introduced in [START_REF] Angeli | On input-to-state stability with respect to decomposable invariant sets[END_REF], [START_REF] Angeli | Characterizations of input-to-state stability for systems with multiple invariant sets[END_REF] (see also [START_REF] Dashkovskiy | Input to state stability and allied system properties[END_REF] for a survey on ISS framework). Definition 4. We say that the system (1) has the practical asymptotic gain (pAG) property if there exist η ∈ K ∞ and a non-negative real q such that for all x ∈ M and all measurable essentially bounded inputs d(•) the solutions are defined for all t ≥ 0 and the following holds:

lim sup t→+∞ |X(t, x; d)| W ≤ η( d ∞ ) + q.
If q = 0, then we say that the asymptotic gain (AG) property holds.

Definition 5. We say that the system (1) has the limit property (LIM) with respect to W if there exists µ ∈ K ∞ such that for all x ∈ M and all measurable essentially bounded inputs d(•) the solutions are defined for all t ≥ 0 and the following holds:

inf t≥0 |X(t, x; d)| W ≤ µ( d ∞ ).
Definition 6. We say that the system (1) has the practical global stability (pGS) property with respect to W if there exist β ∈ K ∞ and q ≥ 0 such that for all x ∈ M and measurable essentially bounded inputs d(•) the following holds for all t ≥ 0:

|X(t, x; d)| W ≤ q + β(max{|x| W , d ∞ }).
It has been shown in [START_REF] Angeli | On input-to-state stability with respect to decomposable invariant sets[END_REF], [START_REF] Angeli | Characterizations of input-to-state stability for systems with multiple invariant sets[END_REF] that to characterize pAG property in terms of Lyapunov functions the following notion is appropriate.

Definition 7. We say that a

C 1 function V : M → R is a practical ISS-Lyapunov function for (1) if there exists K ∞ functions α 1 , [α 2 ]
, α 3 and γ, and scalar q ≥ 0 [and c ≥ 0] such that

α 1 (|x| W ) ≤ V (x) ≤ [α 2 (|x| W + c)],
the function V is constant on each W i and the following dissipation holds:

DV (x)f (x, d) ≤ -α 3 (|x| W ) + γ(|d|) + q.
If the latter inequality holds for q = 0, then V is said to be an ISS-Lyapunov function.

Notice that α 2 and c are in square brackets as their existence follows (without any additional assumptions) by standard continuity arguments.

The main result of [START_REF] Angeli | On input-to-state stability with respect to decomposable invariant sets[END_REF], [START_REF] Angeli | Characterizations of input-to-state stability for systems with multiple invariant sets[END_REF] connecting these robust stability properties is stated below, it extends the results of [START_REF] Sontag | On characterizations of input-to-state stability with respect to compact sets[END_REF], [START_REF] Sontag | New characterizations of input-to-state stability[END_REF] obtained for connected sets.

Theorem 1. Consider a nonlinear system as in (1) and let a compact invariant set containing all αand ω-limit sets of (2)

W be decomposable (in the sense of Definition 3). Then the following facts are equivalent. 1. The system admits an ISS Lyapunov function; 2. The system enjoys the AG property; 3. The system admits a practical ISS Lyapunov function; 4. The system enjoys the pAG property; 5. The system enjoys the LIM property and the pGS.

Definition 8. [START_REF] Angeli | Characterizations of input-to-state stability for systems with multiple invariant sets[END_REF] Suppose that a nonlinear system as in (1) satisfies the assumptions and the list of equivalent properties of Theorem 1. Then this system is called ISS with respect to the set W .

III. MULTISTABLE SYSTEMS

ẋ(t) = F (x t , d t ), x 0 ∈ C τ , (3)
where the map F :

C τ × D → T x M is of class C 1 (we will denote a set of continuous functions ξ : [-τ, 0] → M by C τ ),
x(t) ∈ M is the state, x t ∈ C τ and d t ∈ D for all t ≥ 0. We denote by X(t, x 0 ; d) the uniquely defined solution of (3) at time

t fulfilling X(θ, x 0 ; d) = x 0 (θ) for all θ ∈ [-τ, 0]; X x0,d t (θ) = X(t + θ, x 0 ; d) for θ ∈ [-τ, 0]. Define as in [42] |x t | = max θ∈[-τ,0] |x(t + θ)|, ||x|| t0 = sup t≥t0 |x t | = sup t≥t0-τ |x(t)|.
Again, together with (3), we will analyze its unperturbed version:

ẋ(t) = F (x t , 0). (4)
A set S ⊂ C τ is invariant for the unperturbed system (4) if X x0,0 t ∈ S for all t ∈ R + and for all x 0 ∈ S. Define the distance from a function ξ ∈ C τ to a set S ⊂ C τ as ||ξ|| S = min α∈S |ξ -α|.

Let W ⊂ M be a set, denote by W a subset of

W = {ξ ∈ C τ : ξ(t) ∈ W ∀t ∈ [-τ, 0]} such that if ζ ∈ W then ζ = X ξ,0 τ for ξ ∈ W.
For stability analysis in time-delay systems it is required to define a distance to invariant sets in two spaces: in R n with respect to the set W and in C τ with respect to corresponding invariant set W (functions from C τ taking values in W and solutions of ( 3)). The following stability notions for (3) are considered in this work (for a recent survey on stability tools for time-delay systems see [START_REF] Fridman | Tutorial on Lyapunov-based methods for time-delay systems[END_REF]). Definition 9. The system (3) has the pAG property with respect to the set W if there exist η ∈ K ∞ and a non-negative real q such that for all x 0 ∈ C τ and all bounded piecewise continuous inputs d(•) the solutions are defined for all t ≥ 0 and the following holds:

lim sup t→+∞ |X(t, x 0 ; d)| W ≤ η( d t 0 ) + q.
If q = 0, then we say that the AG property holds.

This property can be equivalently stated as

lim sup t→+∞ ||X x0,d t || W ≤ η( d t 0 ) + q
and it implies that (a subset of) W is invariant for (4) if q = 0.

Definition 10. The system (3) has the pGS property with respect to the set W if there exist β ∈ K ∞ and q ≥ 0 such that for all x 0 ∈ C τ and all bounded piecewise continuous inputs d(•) the following holds for all t ≥ 0:

|X(t, x 0 ; d)| W ≤ q + β(max{||x 0 || W , d t 0 }).
To characterize pAG and pGS properties for a time-delay system (3) the Lyapunov-Razumikhin approach is used in this work [START_REF] Pepe | On the Liapunov-Krasovskii methodology for the ISS of systems described by coupled delay differential and difference equations[END_REF], [START_REF] Dashkovskiy | Lyapunov-Razumikhin and Lyapunov-Krasovskii theorems for interconnected ISS time-delay systems[END_REF]. Given a continuous function

x : [-τ, +∞) → M with a C 1 function U : M → R denote U (t) = U (x(t)), if x(t) = X(t, x 0 ; d)
D + U (t) = lim sup h→0 + U (t + h) -U (t) h . Definition 11. A C 1 function U : M → R is a practical ISS-Lyapunov-Razumikhin (ISS-LR) function for (3) if there exist K ∞ functions α 1 , [α 2 ]
, α 4 , γ and γ U , γ U (s) < s for all s > 0, and scalar q ≥ 0 [and c ≥ 0] such that

α 1 (|x| W ) ≤ U (x) ≤ [α 2 (|x| W + c)], U (t) ≥ max{γ U (|U t |), γ(|d t |), q} ⇒ D + U (t) ≤ -α 4 [U (t)].
If the latter inequality holds for q = 0, then U is said to be an ISS-LR function.

Definition 12. The system in ( 3) is said to be ISS with respect to the set W if it admits pAG and pGS properties with respect to the set W.

Note that definitions 8 and 12 introduce the same property, but for different classes of systems, ( 1) and ( 3), respectively.

The following result can be stated connecting pAG, pGS properties and the existence of an ISS-LR function.

Theorem 2. Consider the system (3). Suppose there exists an ISS-LR function U : M → R as in Definition 11. Then the system (3) admits the pAG property from Definition 9 with η(s) = α -1 1 • γ(s) and the pGS property from Definition 10.

Proof. By using Lemma 1 of [START_REF] Teel | Connections between Razumikhin-type theorems and the ISS nonlinear small gain theorem[END_REF] and Definition 11, it follows that for all t ≥ 0:

U (t) ≤ max{χ[U (0), t], γ U (||U t || 0 ), γ(||d t || 0 ), q} (5)
for some χ ∈ KL (χ(s, 0) ≥ s for all s ≥ 0). In addition, for ϕ(s) = 0.5[1sign(s -τ )]:

|U t | ≤ max{|U 0 |ϕ(t), sup t≥0 U (t)} (6)
for all t ≥ 0 (this estimate is true by definition of the norm). By substituting ( 5) in ( 6) and taking the supremum of the left-hand side of (6) we obtain:

||U t || 0 ≤ max{|U 0 |ϕ(t), χ[U (0), 0], γ U (||U t || 0 ), γ(||d t || 0 ), q} ≤ max{χ(|U 0 |, 0), γ U (||U t || 0 ), γ(||d t || 0 ), q}.
Since γ U (s) < s for all s > 0 by assumption, the boundedness of U (t) can be proven [START_REF] Teel | Connections between Razumikhin-type theorems and the ISS nonlinear small gain theorem[END_REF], i.e.,

||U t || 0 ≤ max{χ(|U 0 |, 0), γ(||d t || 0 ), q}.
From Definition 11, this estimate implies (recall that α(a + b) ≤ α(2a) + α(2b) for a function α ∈ K for any a ≥ 0, b ≥ 0)

|X(t, x 0 ; d)| W ≤ α -1 1 [max{χ(α 2 (||x 0 || W + c), 0), γ(||d t || 0 ), q}] ≤ max{α -1 1 • χ(α 2 (2||x 0 || W ), 0), α -1 1 • γ(||d t || 0 )} +α -1 1 • χ(α 2 (2c), 0) + α -1 1 (q) ≤ β(max{||x 0 || W , ||d t || 0 }) + q, where β(s) = α -1 1 • max{χ[α 2 (2s), 0], γ(s)} and q = α -1 1 • χ(α 2 (2c), 0) + α -1 1 (q)
. This implies that the system (3) possesses the pGS property.

To prove asymptotic convergence consider t > 2τ , then by substituting ( 6) in ( 5) we obtain:

U (t) ≤ max{χ[U (0), t], γ U [sup t≥0 U (t)], γ(||d t || 0 ), q}.
Again γ U (s) < s for all s > 0, and for a sufficiently big T > 0 [START_REF] Teel | Connections between Razumikhin-type theorems and the ISS nonlinear small gain theorem[END_REF]:

sup t≥2τ +T U (t) ≤ max{χ[U (0), t], γ(||d t || 0 ), q}.
Next, by repeating the arguments given above, asymptotic convergence can be proven, i.e.,

lim sup t→+∞ U (t) ≤ max{γ( d t 0 ), q}, (7)
or, equivalently, lim sup

t→+∞ |X(t, x 0 ; d)| W ≤ α -1 1 • γ( d t 0 )] + α -1 1 (q)
completing the proof.

IV. ISS OF MULTISTABLE SYSTEMS WITH DELAYED PERTURBATIONS

In this section we consider the robustness of the system (1) with respect to a disturbance d, which is dependent on a delayed state. The analysis is conducted under the assumption that the system (1) is ISS with respect to a set W. Furthermore, the proposed approach is illustrated via the well-known example of a nonlinear pendulum with delay.

A. Robustness analysis

If ( 1) is ISS with respect to the set W, then by Theorem 1 there exists an ISS Lyapunov function V as in Definition 7.

From the inequalities α

3 [0.5α -1 2 • V (x)] ≤ α 3 (0.5[|x| W + c]) ≤ α 3 (|x| W ) + α 3 (c) we obtain DV (x)f (x, d) ≤ -α 4 [V (x)] + γ(|d|) + q,
where α 4 (s) = α 3 [0.5α -1 2 (s)] and q = q + α 3 (c). Assume that the input d has two terms d 1 and d 2 , and d 2 is a function of x t ∈ C τ for some τ > 0, i.e.:

d = d 1 + d 2 , d 2 = g(x t ), (8)
where g is a continuous function, |g(x t )| ≤ υ(|V t |) + υ 0 for υ ∈ K ∞ and υ 0 ≥ 0. Denote further for simplicity of notation d = d 1 , then the system (1) is transformed to (3) with

F (x t , d t ) = f (x(t), d + g(x t )),
and

D + V (t) ≤ -α 4 (V (t)) + γ(2υ(|V t |) + 2υ 0 ) + γ(2|d t |) + q.
This estimate can be rewritten as follows:

V (t) ≥ max{γ V (|V t |), γ(|d t |), q} ⇒ D + V (t) ≤ -0.5α 4 (V (t)), γV (s) = α -1 4 [6γ(4υ(s))], γ(s) = α -1 4 [6γ(2s)], q = α -1 4 [6q + 6γ(4υ 0 )].
It is straightforward to see that if γV (s) < s for all s > 0, then V is an ISS-LR function for (1) with ( 8), and by Theorem 2 this system possesses pAG and pGS properties.

B. Illustration for a nonlinear pendulum

Now, the procedure for a robust ISS analysis of a multistable system with delays outlined in Section IV-A is illustrated via the example of a nonlinear pendulum. First, we prove the assumption made in Section IV-A that the pendulum is ISS with respect to a set W. Second, a condition for ISS of a pendulum with delay is derived. During our analysis, we also establish almost global attractivity of an equilibrium of a nonlinear pendulum with constant nonzero input. To the best of our knowledge, such result is not available in the literature thus far.

1) Delay-free case: Consider a nonlinear pendulum:

ẋ1 = x 2 , ẋ2 = -Ω 2 sin(x 1 ) -κx 2 + d, (9)
where the state x = [x 1 , x 2 ] takes values on the cylinder M := S × R, d(t) ∈ R is an exogenous disturbance, and Ω, κ are constant positive parameters. The total energy of ( 9) is H(x) = 0.5x 2 2 + Ω 2 (1 -cos(x 1 )) and Ḣ = x 2 d -κx 2 2 . The unperturbed system (9) has two equilibria [0, 0] and [π, 0] (the former is attractive and the latter one is a saddle-point). Thus, W = {[0, 0] ∪ [π, 0]} is a compact set containing all αand ω-limit sets of (9) for d = 0. In addition, it is straightforward to check that W is decomposable in the sense of Definition 3.

Lemma 1. The system ( 9) is ISS with respect to the set W.

Proof. Following the ideas of [START_REF] Angeli | Stability robustness in the presence of exponentially unstable isolated equilibria[END_REF], consider a Lyapunov function candidate

V (x) = H(x) + κ (1 -cos(x 1 )) + x 2 sin(x 1 ), (10)
which is positive definite for any

0.5[κ - √ κ 2 + 4Ω 2 ] ≤ ≤ 0.5[κ + √ κ 2 + 4Ω 2 ]. Indeed, 1 -cos(x 1 ) ≥ 0.5(1 -cos 2 (x 1 ))
for any x 1 ∈ S, then

V (x) = 0.5x 2 2 + [Ω 2 + κ ](1 -cos(x 1 )) + x 2 sin(x 1 ) ≥ 0.5x 2 2 + 0.5[Ω 2 + κ ](1 -cos 2 (x 1 )) + x 2 sin(x 1 ) = 0.5x 2 2 + 0.5[Ω 2 + κ ] sin 2 (x 1 ) + x 2 sin(x 1 ) = 1 2 sin(x 1 ) x 2 Y sin(x 1 ) x 2 , Y = Ω 2 + κ 1 ,
and the matrix Y is positive definite for 2

∈ [κ - √ κ 2 + 4Ω 2 , κ + √ κ 2 + 4Ω 2 ]. Next, V = x 2 d -κx 2 2 + κ sin(x 1 )x 2 + x 2 2 cos(x 1 ) + sin(x 1 )[d -Ω 2 sin(x 1 ) -κx 2 ] = -[κ -cos(x 1 )]x 2 2 -Ω 2 sin 2 (x 1 ) (11)
+ sin(x 1 )d + x 2 d.

Thus, for further consideration select 0

< ≤ 0.5[κ + √ κ 2 + 4Ω 2 ], then V ≤ -0.5[κ -]x 2 2 -0.5 Ω 2 sin 2 (x 1 ) (12)
+0.5[ Ω -2 + 1 κ - ]d 2
and V is an ISS Lyapunov function for [START_REF] Dashkovskiy | Input to state stability and allied system properties[END_REF] provided that 0 < < min{κ, 0.

5[κ + √ κ 2 + 4Ω 2 ]} = κ. The result follows from Theorem 1.
Using this result it is possible to prove that for a constant input d (with d < Ω 2 ) the pendulum still has two steady-state points with similar stability properties.

Lemma 2. Let d < min{Ω 2 , λmin(Y ) 2 π ζ , 0.5 √ Ω π ζ
, ξ} be a constant input in [START_REF] Dashkovskiy | Input to state stability and allied system properties[END_REF], where

= min κ - 1 + , 1 √ 2π Ω 2 (Ω 2 + (κ + 1) ) , ζ = √ 2π[ Ω -2 + 1 κ - ], ξ = 2 √ Ω 2 + κ ζ Ω 2 + (κ + 1) Ω 2 + 1 √ 2π
and 0 < < min{1, κ} is a parameter. Then the system has two equilibria, [arcsin(dΩ -2 ), 0] and [π -arcsin(dΩ -2 ), 0], the former one is almost globally attractive.

Proof. It is straightforward to verify that for d < Ω 2 the system (9) has two equilibrium points in M . In order to show that there is no another invariant solution and to investigate stability of these equilibriums we can use ISS property established in Lemma 1. From the proof of Lemma 1 we obtain that for an ISS Lyapunov function V in (10) its derivative satisfies (12) for 0 < < κ. Additionally, from ( 10) and ( 12) we have the following series of inequalities:

V (x) ≤ 0.5[(1 + )x 2 2 + (Ω 2 + (κ + 1) )x 2 1 ] ∀x ∈ M, V ≤ -0.5[κ -]x 2 2 -0.5 Ω 2 √ 2π x 2 1 +0.5[ Ω -2 + 1 κ - ]d 2 ∀x ∈ M 1 , V (x) ≥ 0.5[(1 -)x 2 2 -(Ω 2 + (κ + 1) )(x 1 -π) 2 ] +2(Ω 2 + κ ) ∀x ∈ M 2 , V ≤ -0.5[κ -]x 2 2 -0.5 Ω 2 √ 2π (x 1 -π) 2 +0.5[ Ω -2 + 1 κ - ]d 2 ∀x ∈ M 2 ,
where

M 1 := {x ∈ M : |x 1 | ≤ 0.5π} and M 2 := {x ∈ M : 0.5π ≤ x 1 ≤ 1.5π}.
Then from the first two inequalities we obtain for all x ∈ M 1 :

V ≤ -V + 0.5[ Ω -2 + 1 κ - ]d 2 and M d,0 = {x ∈ M : V (x) ≤ 0.5 -1 [ Ω 2 + 1 κ-]d 2 } is an invariant set if it is contained in M 1 . From the proof of Lemma 1 we know that V (x) ≥ λ min (Y )(x 2 2 + sin 2 (x 1 )),
where λ min (Y ) = 0.5(

Ω 2 + κ + 1 -(Ω 2 + κ -1) 2 + 4 2 )
is the minimal eigenvalue of the matrix Y defined there. Since

V (x) ≥ λ min (Y ) sin 2 (x 1 ) ≥ λmin(Y ) √ 2π x 2 1 for x ∈ M 1 , then we obtain that M d,0 ⊂ M 1 if |x 1 | ≤ √ 2π 2λmin(Y ) -1 [ Ω 2 + 1 κ-]|d| ≤ π 2 or |d| ≤ λmin(Y ) 2 π ζ . In this case V (x) ≤ π 3/2 4 √ 2 λ min (Y ) for x ∈ M 1 .
In the set M 2 the function V has a saddle point at [π, 0] and the derivative of V is negative-definite outside the set

M d,π = {x ∈ M 2 : [κ -]x 2 2 + Ω 2 √ 2π (x 1 -π) 2 ≤ [ Ω -2 + 1 κ-]d 2 } and V (x) ≥ 2(Ω 2 + κ ) -0.5(Ω 2 + (κ + 1) )(x 1 -π) 2 for x ∈ M d,π if 0 < < min{1, κ}. Note that M d,π ⊂ M 2 for |d| ≤ 0.5 √ Ω π ζ and the levels of V (x) are separated into the sets M d,0 and M d,π if |d| < ξ.
Assume that all these restrictions on d are satisfied, i.e. d < min{Ω 2 ,

λmin(Y ) 2 π ζ , 0.5 √ Ω π ζ , ξ}, then by ISS property asymptotically lim sup t→+∞ |x(t)| W ≤ η( d ∞ )
for some η ∈ K ∞ with W = {[0, 0] ∪ [π, 0]}, and due to compactness of W the variable x(t) is bounded. By consideration above, asymptotically x(t) ∈ M d,0 ∪M d,π and both equilibria x a = [arcsin(dΩ -2 ), 0] and x r = [π-arcsin(dΩ -2 ), 0] belong to this intersection (at these steady-states ẋ = 0 and, hence, V = 0, then all these points are inside M d,0 ∪ M d,π by construction).

Let us show that x a and x r are the only invariant solutions in these sets. For this purpose consider

W (x) = 0.5x 2 2 + Ω 4 -d 2 + d[arcsin(dΩ -2 ) -x 1 ] -Ω 2 cos(x 1 ),
then W : R 2 → R is a C 1 function and W : M → R + is a discontinuous one (depending on the definition of the state space).

Note that W (x a ) = 0 is the global minimum of W in M × R, and

W (x r ) = 2 √ Ω 4 -d 2 + d(2 arcsin(dΩ -2 ) -π) > 0 is a
local maximum (W is monotonously growing with respect to |x 2 | and ∂W ∂x1 = 0 at two points x a and x r ). For a constant d we obtain

Ẇ = x 2 (-Ω 2 sin(x 1 ) -κx 2 + d) -dx 2 + Ω 2 sin(x 1 )x 2 = -κx 2 2 ≤ 0.
Let discontinuity of W be at x 1 = 0 and consider the set M d,π . Recall that x r is the only steady-state contained in M d,π . Next, we show by contradiction that x r is the only invariant solution contained in M d,π . To this end, assume that there is another positively invariant solution x * (t) ∈ M d,π for all t ≥ 0. Since x(t) is bounded, W is continuous on M d,π with a bounded image and Ẇ ≤ 0 for all x ∈ M d,π , then by LaSalle's invariance principle, x * (t) has to converge to the largest invariant set contained in {x ∈ M d,π : Ẇ ≡ 0}. Clearly, for x ∈ M d,π , Ẇ ≡ 0 implies x(t) = x r for all t ≥ 0. But x r is a saddle point and, hence, not attractive. Therefore, x r is the only invariant solution contained in M d,π . Consequently, any trajectory x(t) with x(0) ∈ M d,π \ {x r } must exit the set M d,π at some instant in time (since Ẇ < 0 there and x r is a saddle of W ).

Outside of M d,0 ∪ M d,π we have V < 0 and it means that the set M d,0 is attractive. To analyze the system behavior inside the invariant set M d,0 , let the discontinuity of W be at x 1 = π, again since x(t) is bounded, W is continuous on M d,0 and Ẇ ≤ 0, then x(t) has to converge to the largest invariant set into Ẇ = 0, that is x a .

2) A delayed case study: Now consider a time-delay modification of (9):

ẋ1 (t) = x 2 (t), ẋ2 (t) = -Ω 2 sin[x 1 (t -τ )] -κx 2 (t) + d(t), (13)
where τ > 0 is a fixed delay. The unperturbed system [START_REF] Farhangi | The path of the smart grid[END_REF] with d(t) = 0 has the same equilibria as [START_REF] Dashkovskiy | Input to state stability and allied system properties[END_REF], i.e. [0, 0] and [π, 0].

The system (13) can be represented as follows:

ẋ1 (t) = x 2 (t), ẋ2 (t) = -Ω 2 sin[x 1 (t)] -κx 2 (t) +d(t) + Ω 2 {sin[x 1 (t)] -sin[x 1 (t -τ )]}.
By the mean value theorem

| sin[x 1 (t)] -sin[x 1 (t -τ )]| = | cos[x 1 (φ)]x 2 (φ)τ | ≤ |x 2 (φ)|τ
for some φ ∈ [t -τ, t]. Thus, the system (13) can be analyzed as a perturbed nonlinear pendulum with part of the input d dependent on the delay. By taking the estimate derived for V in [START_REF] Efimov | Oscillatority of nonlinear systems with static feedback[END_REF] we obtain for µ = Ω -2 + 1 κ-:

D + V (t) ≤ -0.5[κ -]x 2 2 -0.5 Ω 2 sin 2 (x 1 ) +µΩ 4 x 2 2 (φ)τ 2 + µd 2 .
It is straightforward to check that

V (x) ≤ 0.5[1 + ]x 2 2 + 0.5 sin 2 (x 1 ) + 2[Ω 2 + κ ], x 2 2 ≤ 2 1 - V (x) + 1 - for 0 < < min{1, κ}, then for ρ = min{ κ- 1+ , Ω 2 } D + V (t) ≤ -ρ{V (t) -2[Ω 2 + κ ]} +µΩ 4 x 2 2 (φ)τ 2 + µd 2 ≤ -ρ{V (t) -2[Ω 2 + κ ]} + µΩ 4 1 - τ 2 [2V (φ) + ] + µd 2 .
Therefore,

V (t) ≥ 6 ρ max{2 µΩ 4 1 - τ 2 |V t |, 2ρ[Ω 2 + κ ] + µΩ 4 1 - τ 2 , µd 2 } ⇒ (14) D + V (t) ≤ -0.5ρV (t)
and V is an ISS-LR function for [START_REF] Farhangi | The path of the smart grid[END_REF] provided that

12 ρ µΩ 4 1 - τ 2 < 1. (15)
The inequality ( 15) is a delay-dependent stability condition for [START_REF] Farhangi | The path of the smart grid[END_REF], which is always satisfied for a sufficiently small delay τ .

The set of asymptotic attraction for ( 13) can be evaluated from [START_REF] Franci | Desynchronization and inhibition of Kuramoto oscillators by scalar mean-field feedback[END_REF].

Remark 1. If we assume that max{0, κ-Ω 2 1+Ω 2 } < < min{1, κ}, then min{ κ- 1+ , Ω 2 } = κ- 1+ and the condition (15) can be rewritten as follows:

τ 2 < 1 12Ω 2 1 - 1 + 1 (κ -) + Ω 2 .
Since the functions 1- 1+ and 1 (κ-)+Ω 2 are decreasing for ∈ (max{0, κ-Ω 2 1+Ω 2 }, min{1, κ}), selecting = max{0, κ-Ω 2 1+Ω 2 } + ε for a sufficiently small ε > 0 optimizes the value of the admissible delay τ to

τ * = 1 2Ω 1 - 1 + 1/3 (κ -) + Ω 2 ,
i.e. for any τ < τ * the system (13) admits V as an ISS-LR function.

V. APPLICATION TO A MICROGRID COMPOSED OF TWO DROOP-CONTROLLED INVERTERS WITH DELAY

In this section the theoretical results of Section III are applied to our main motivating application: a droop-controlled microgrid with delays. In particular, we are interested in conditions for ISS of such systems. In order to tackle this problem, we proceed along the lines detailed in Section IV. The analysis is conducted under a reasonable assumption of constant voltage amplitudes. Then, a lossless droop-controlled microgrid formed by two inverters with delay can be modeled as [START_REF] Schiffer | Conditions for stability of droop-controlled inverter-based microgrids[END_REF]:

θ(t) = ω 1 (t) -ω 2 (t), (16)
τ P1 ω1 (t) = -ω 1 (t) -k P1 a 12 sin[θ(t -τ d1 )] + c 1 + d 1 (t), τ P2 ω2 (t) = -ω 2 (t) + k P2 a 12 sin[θ(t -τ d2 )] + c 2 + d 2 (t),
where θ(t) ∈ [0, 2π) is the phase difference in inverters, ω 1 (t), ω 2 (t) ∈ R are time-varying frequencies of the inverters; τ d1 > 0 and τ d2 > 0 are delays caused by the digital controls required to implement the droop controls;

τ P1 > 0, τ P2 > 0, k P1 > 0, k P2 > 0, a 12 > 0, c 1 and c 2 = - k P 2 k P 1
c 1 are constant parameters, the disturbances d 1 (t) and d 2 (t) represent additional model uncertainties. We say that a solution of ( 16) is phase-locked if θ(t) = θ 0 is constant ∀t ∈ R + for some θ 0 ∈ [0, 2π) [START_REF] Franci | Desynchronization and inhibition of Kuramoto oscillators by scalar mean-field feedback[END_REF]. If this property holds asymptotically, i.e., for t → +∞, we speak about an asymptotic phase-locking.

For brevity of presentation, we impose the following restrictions on the values of parameters.

Assumption 1. τ P1 = τ P2 = τ P > 0 and τ d1 = τ d2 = τ > 0.

Under this assumption, define the new coordinates: [START_REF] Green | Control of inverter-based micro-grids[END_REF]. The solid lines show the state trajectories for the case d 1 (t) = d 2 (t) = 0. The dashed lines correspond to the case d 1 (t) = 0.8 sin(3t), d 2 (t) = 0.9 sin(5t).

x 1 = θ, x 2 = ω 1 -ω 2 , x 3 = k P2 k P1 ω 1 -ω 2 ,
then the system ( 16) can be rewritten as follows:

ẋ1 (t) = x 2 (t), (17)
τ P ẋ2 (t) = -x 2 (t) -[k P1 + k P2 ]a 12 sin[x 1 (t -τ )] +[1 + k P2 k P1 ]c 1 + d 1 -d 2 , (18)
τ P ẋ3 (t) = -x 3 (t) + k P2 k P1 d 1 -d 2 . ( 19
)
Thus, the system ( 16) is decomposed into two independent subsystems: ( 17), ( 18) and (19). The variable x 3 converges asymptotically to zero with the time constant τ P if d 1 = d 2 = 0. Hence, asymptotically the frequencies ω 1 and ω 2 are locked. The dynamics [START_REF] Guckenheimer | Structurally stable heteroclinic cycles[END_REF], [START_REF] Guerrero | Advanced control architectures for intelligent microgrids -part I: Decentralized and hierarchical control[END_REF] have the form of ( 13

for 0 < < min{1, τ -1 P }. Therefore, for a sufficiently small delay τ the inverters will demonstrate a phase-locking behavior. According to [START_REF] Nussbaumer | Comparison of prediction techniques to compensate time delays caused by digital control of a three-phase buck-type PWM rectifier system[END_REF], a good estimate of the overall delay introduced by the digital control is τ = 1.75T S 1 , where T S = 1/f S and f S ∈ R >0 is the switching frequency of the inverter. Since usually f S ∈ [START_REF] Angeli | Stability robustness in the presence of exponentially unstable isolated equilibria[END_REF][START_REF] Christopher | Input-to-state stability, integral input-to-state stability, and unbounded level sets[END_REF] kHz [START_REF] Green | Control of inverter-based micro-grids[END_REF], τ is reasonably small in most practical applications. Hence, we expect condition [START_REF] Christopher | Input-to-state stability, integral input-to-state stability, and unbounded level sets[END_REF] to be satisfied for most practical choices of parameters τ P , k P1 and k P2 .

The analysis is illustrated in a simulation example with the following set of parameters for the system (16): τ P = 1, k P1 = 10, k P2 = 20, a 12 = 0.1, c 1 = 0.2 and τ = 0.05. Condition ( 20) is satisfied for = 0.5 min{1, τ -1 P }. The simulation results are shown in Fig. 1. The solid lines represent the state (θ, ω 1 , ω 2 ) T trajectories for the case d 1 (t) = d 2 (t) = 0, and the dashed lines correspond to d 1 (t) = 0.8 sin(3t), d 2 (t) = 0.9 sin(5t). The phase-locking phenomenon is observed in these simulation results.

VI. CONCLUSIONS

Sufficient conditions for ISS of multistable systems with delay have been derived. The conditions have been established using Lyapunov-Razumikhin functions. The potential of the presented approach has been illustrated by exhibiting several new robustness properties for a nonlinear pendulum with delay. Furthermore, it has been shown that asymptotic phase-locking in a lossless droop-controlled microgrid formed by two inverters with delays can be analyzed based on a perturbed pendulum model. By exploiting this fact, a delay-dependent condition for ISS of such a microgrid has been presented. Future work will consider an extension of the analysis to more complex inverter models with delays (e.g., time-varying voltages or internal filter and controller dynamics).

  WITH DELAYS Let τ > 0, for a function d : [-τ, +∞) → R m and t ≥ 0 denote a function d t (•) : [-τ, 0] → R m defined by d t (θ) = d(t+θ) for θ ∈ [-τ, 0]. Denote by D a set of bounded and piecewise continuous functions d t (•) : [-τ, 0] → R m . Consider a functional differential equation on an n-dimensional C 2 connected and orientable Riemannian manifold M without a boundary:

  is a solution to (3) for some piecewise continuous d : [-τ, +∞) → R m and initial condition x 0 ∈ C τ , then the upper right-hand side derivative of U along this solution is

2 ωFigure 1 .

 21 Figure1. Simulation results for the system[START_REF] Green | Control of inverter-based micro-grids[END_REF]. The solid lines show the state trajectories for the case d 1 (t) = d 2 (t) = 0. The dashed lines correspond to the case d 1 (t) = 0.8 sin(3t), d 2 (t) = 0.9 sin(5t).

  ]c 1 + d 1 -d 2 and, as it has been established above, have pAG and pGS properties from definitions 9 and 10 respectively if condition (15) is satisfied, which for (17),[START_REF] Guerrero | Advanced control architectures for intelligent microgrids -part I: Decentralized and hierarchical control[END_REF] takes

				k P 2
				k P 1
	the form:	τ 2 <	12	min [k P 1 +k P 2 ] 2 a 2 τ -1 P -1+ , 12 τ 2 P (1-) [k P 1 +k P 2 ]a12 + 1 [k P 1 +k P 2 ]a12 τ P 1-τ P

) for d = [1 +

The overall delay reduces to τ = 1.5T S if no moving average function for the measurement is used[START_REF] Nussbaumer | Comparison of prediction techniques to compensate time delays caused by digital control of a three-phase buck-type PWM rectifier system[END_REF].


Mohamed Hadded
email: mohamed.hadded@it-sudparis.eu

Anis Laouiti
email: anis.laouiti@it-sudparis.eu

Rachid Zagrouba
email: rachid.zagrouba@cristal.rnu.tn

Paul Muhlethaler
email: paul.muhlethaler@inria.fr

Leila Azouz Saidane
email: leila.saidane@ensi.rnu.tn

A Fully Distributed TDMA based MAC Protocol for Vehicular Ad Hoc Networks

Keywords: VANET, MAC Protocol, collision-free, TDMA, Fully Distributed, Scheduling Scheme

The Vehicular Ad-Hoc NETwork (VANET) consists of a set of vehicles moving on roads which can communicate with each other through ad hoc wireless devices. VANET has attracted a lot of attention in the research community in recent years with the main focus on its safety applications. One of the challenges for vehicular network is the design of an efficient Medium Access Control (MAC) protocol due to the hidden node problem, the high speed of the nodes, the frequent changes in topology, the lack of an infrastructure, and various QoS requirements. Motivated by this observation, we design a fully distributed and locationbased TDMA scheduling scheme for VANETs networks, named DTMAC. The main goal of this work is to propose a MAC protocol that can provide fairness in accessing the transmission medium, as well as reduce access collision and merging collision under various conditions of vehicular density without having to use expensive spectrum and complex mechanisms such as CDMA or OFDMA. An analytical model of the average access collision probability and throughput are derived which can be used to evaluate the performance of DTMAC protocol as well as to validate the simulation results under different traffic conditions.

I. INTRODUCTION

Increasing road traffic accidents in the world have motivated the evolution of Intelligent Transportation Systems (ITS) and other applications to improve road safety and driving comfort. A communication network, called Vehicular Ad-hoc NETwork (VANET) in which the vehicles are equipped with wireless devices has been developed to make these applications possible. In a VANET, communications can either be Vehicle To Vehicle (V2V) or Vehicle To Infrastructure (V2I) [START_REF] Hadded | Tdma-based mac protocols for vehicular ad hoc networks a survey, qualitative analysis and open research issues[END_REF]. Based on these two types of communications, a VANET can support a wide range of applications for safety (such as dangerous situation detection), for infotainment (such as Internet access and data exchange) and for traffic management (such as vehicle traffic optimization).

Motivated by promising applications of VANET network, The Federal Communication Commission (FCC)

[2] has established a wireless protocol similar to WiFi, called Dedicated Short Range Communications (DSRC) [START_REF] Jiang | Design of 5.9 ghz dsrc based vehicular safety communication[END_REF] in order to make V2V communication an effective reality. The DSRC radio technology is defined in the frequency band of 5.9 GHz with a total bandwidth of 75 MHz. This band is divided into 7 channels of 10 MHz for each one. These channels comprise one Control CHannel (CCH) reserved for the exchange of periodic and high priority messages and 6 Service CHannels (SCHs) dedicated to data transmission.

Since the safety applications in VANET network have stringent QoS requirement, an efficient Medium Access Control (MAC) protocol that can provide a broadcast service with bounded access delays and minimum transmission collision is required. Recently, MAC protocols, notably those that are based on the TDMA technique are used to enable multiple vehicles to use the same frequency channel without interfering with other vehicles [START_REF] Hadded | Tdma-based mac protocols for vehicular ad hoc networks a survey, qualitative analysis and open research issues[END_REF]. The TDMA principle consists in allocating the bandwidth to all the vehicles by dividing the time into different frames and each frame is divided into several time slots. Each vehicle can access the channel during its dedicated time slot to send data messages, while it can only receive during the time slots reserved for other vehicles. However, many issues arise due to the high vehicle mobility in VANETs which can affect the performance of these protocols. Therefore, the scheduling mechanisms in TDMA based MAC protocols should take into consideration the mobility features of VANETs so as to avoid collisions. In this paper, we propose a completely Distributed and infrastructure free TDMA based MAC protocol (DTMAC) which exploits the linear feature of topology in VANET network. This protocol is based on VeMAC protocol which has been recently proposed for VANET network. DTMAC uses the vehicular location information sufficiently to help the vehicles access the channel in an efficient way, so as to solve the collision problem caused by high mobility of nodes and to reduce the access delay.

The rest of the paper is organized as follows. In Section 2, we review related work. Section 3 describes the system models and presents the TDMA problems that may occur in a fully distributed VANET due to the high mobility of nodes. Section 4 describes our TDMA based MAC protocol, called DTMAC and how it solves the hidden node problem without having to use complex wideband mechanisms such FDMA or CDMA. An analytical model for the average access collision probability and throughput are presented in Section 5. The parameters tuning problem of DTMAC is formulated as a multi-objective optimization problem in Section 6. Finally, conclusions and future work are reported in Section 7.

II. RELATED WORK

Generally, MAC protocols fall into one of two broad categories: contention-based and contention-free. In contentionbased protocols, each node can try to access the channel when it has data to transmit using the carrier sensing mechanism [START_REF] Ye | Congestion control to achieve optimal broadcast efciency in vanets[END_REF]. The IEEE 802.11p [START_REF]IEEE standard for information technology -Telecommunications and information exchange between systems -local and metropolitan area networks -specific requirements part 11 : Wireless LAN medium access control (MAC) and physical layer (PHY) and physical layer (PHY) specifications amendment 6 : Wireless access in vehicular environments Std[END_REF], which is the emerging standard deployed to enable vehicular communication, is a Contentionbased MAC protocol, using a priority-based access scheme that employs both Enhanced Distributed Channel Access (EDCA) and Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanisms [START_REF] Uzcátegui | Wave: A tutorial[END_REF]. Since the IEEE 802.11p standard is a Contention-based MAC, it cannot provide reliable broadcast mechanism with bounded communication delay. This disadvantage is particularly important in VANETs which are specially designed to improve road safety.

In Contention-free MAC protocols, only one vehicle can access the channel at any given time. Therefore, these protocols provide collision-free transmission with bounded access delay for real-time applications. In [START_REF] Lu | Dmmac : A dedicated multichannel mac protocol design for vanet with adaptive broadcasting[END_REF], the authors propose Dedicated Multi-channel MAC (DMMAC) protocol which is an alternative to the IEEE 802.11p standard. DMMAC has an adaptive broadcasting mechanism providing collisionfree and delay-bounded transmissions for safety applications under various traffic conditions. The DMMAC architecture is similar to IEEE 802.11p with the difference that, the CCH Interval is divided into an Adaptive Broadcast Frame (ABF) and a Contention-based Reservation Period (CRP). The ABF period consists of time slots, and each time slot is dynamically reserved by a vehicle as its Basic Channel (BCH) for collision-free delivery of safety messages or other control messages. DMMAC implements a dynamic TDMA mechanism for BCH reservation based on the distributed access technique R-ALOHA (Reliable R-ALOHA [START_REF] Borgonovo | Rr-aloha, a reliable r-aloha broadcast channel for ad-hoc inter-vehicle communication networks[END_REF]). The length of the ABF frame is not uniform in the entire network. Each vehicle dynamically adjusts its ABF length according to its neighbors. Omar et al. developed and evaluated in [START_REF] Zhuang | Vemac: A novel multichannel mac protocol for vehicular ad hoc networks[END_REF], [START_REF] Omar | Evaluation of vemac for v2v and v2r communications under unbalanced vehicle traffic[END_REF], [START_REF]Vemac: A tdma-based mac protocol for reliable broadcast in vanets[END_REF] a contention-free multi-channel MAC protocol proposed for VANETs. In contrast to DMMAC, VeMAC is completely contention-free. This protocol supports efficient one-hop and multi-hop broadcast services on the control channel without the hidden terminal problem caused by node mobility. These broadcast services are presented in [START_REF] Borgonovo | Adhoc mac: new mac architecture for ad hoc networks providing efficient and reliable point-to-point and broadcast services[END_REF] for ADHOC MAC. VeMAC reduces the merging collision rate by assigning disjoint sets of time slots to vehicles moving in opposite directions (Lef t, Right) and to Road Side Units (RSUs). An efficient MAC approach called, ATSA [START_REF] Weidong | Adaptive tdma slot assignment protocol for vehicular ad-hoc networks[END_REF] which is an improvement of the previously proposed MAC protocol based on the VeMAC protocol is named the Decentralized Adaptive TDMA Scheduling Strategy DATS [START_REF] Ke | A decentralized adaptive tdma scheduling strategy for vanet[END_REF]. Like VeMAC, ATSA divides the frame into two sets of time slots Lef t and Right. However in ATSA, when a vehicle accesses the network, it chooses a frame length and competes for one of the time slots available for its direction. Moreover the frame length is dynamically doubled or shortened based on the binary tree algorithm, and the ratio of two slot sets is adjusted to decrease the probability of transmission collisions.

The design of distributed TDMA based MAC protocols for VANETs should consider mobility (i.e., the slots scheduling mechanism should be periodically aware of the neighbors' slot allocation), scalability (i.e., they should scale under different traffic load conditions), and fairness (i.e., all the vehicles have equal access to the medium during a fixed time interval), Packet loss (i.e, hidden nodes and access collision) [START_REF] Hadded | Tdma-based mac protocols for vehicular ad hoc networks a survey, qualitative analysis and open research issues[END_REF]. In this paper, a distributed and infrastructure free TDMA based MAC protocol (DTMAC) is proposed to address above problems. In DTMAC, the road is dissected into small fixed areas in which the time slots will be reused between them in such a way any vehicles in different adjacent areas access to the channel at the same time and thus no interference will occur.

III. SYSTEM MODEL AND TDMA PROBLEM STATEMENT

A. System Model

The VANET network in highway scenario consists of a set of vehicles moving in opposite directions and under different traffic conditions (speed, density). DTMAC is based on the assumption that each vehicle in a VANET is equipped with a GPS (Global Positioning System) or a GALLILEO receiver that also allows it to obtain an accurate real-time three-dimensional geographic position (latitude, longitude and altitude), direction, speed and exact time. Moreover, the synchronization among vehicles may be performed by using GPS timing information. Each road is dissected into small fixed areas (see Figure 2). Note that the area size depends on the transmission range of vehicles (around 1000 m). DTMAC is based on VeMAC protocol, such that the channel time is partitioned into frames and each frame is further partitioned into two sets Lef t and Right. In the next section, we will explain in details the slot scheduling mechanism in DTMAC and we will show how this protocol can provide an efficient time slot utilization for the participating vehicles while minimizing transmission collisions due to the hidden node problem.

B. TDMA Problem Statement

When a distributed scheme is used to allocate a time slot, two types of collision can occur [START_REF] Borgonovo | Impact of user mobility on the broadcast service efficiency of the adhoc mac protocol[END_REF]: access collision between vehicles trying to access the same available time slots, and merging collisions between vehicles using the same time slots. When the traffic density is high, the rate of access and merging collisions will increase rapidly which will lead to inefficient channel utilization and high access delay for safety application.

An access collision problem occurs when two or more vehicles within the same two-hop neighborhood set attempt to access the same available time slot. This problem is likely to happen when a distributed scheme is used. On the other hand, merging collisions occur when two vehicles in different two-hop sets accessing the same time slot become members of the same two-hop set due to changes in their position. Generally, in VANETs, merging collisions are likely to occur in the following cases:

• Vehicles moving at different speeds.

• Vehicles moving in opposite directions.

• There are RSUs installed along the road. Figure 1 shows an example of the second case of the merging collision problem, when vehicle B in the first twohop set moving in the opposite direction to vehicle E in the second two-hop set is using the same time slot as B. Since B and E become members of the same two-hop set, a collision occurs.

IV. DISTRIBUTED AND INFRASTRUCTURE FREE TDMA BASED MAC PROTOCOL

A. DTMAC Preliminaries

We propose a completely distributed and infrastructure free TDMA scheduling scheme which exploits the linear feature of topology in VANET network. Indeed, the vehicles motions in highway environment are linear due to the fact that their movements are constrained by the road topology. Our scheduling mechanism is also based on the assumption that each road is dissected into small fixed areas, denoted by x i , i = 1, . . . , N (see Figure 2).

The time slots in each TDMA frame are equally partitioned into two sets Lef t and Right, associated with the vehicles that are moving on the left and right direction, respectively (see Figure 3). Moreover, the Lef t and Right sets are further divided into three sets associated with vehicles in three contiguous areas: S 0 , S 1 and S 2 , receptively (see Figure 3). Each frame consists of a constant number of time slots, denoted by T and each time slot is of a fixed time duration, denoted by s. Each vehicle can detect the start time of each frame as well as the start time of a time slot. In the studied VANET network, all vehicles are equipped with a Global Position System (GPS) and thus the one-Pulse-Per-Second (1PPS) signal that a GPS receiver gets every second from GPS satellites can be used for slot synchronization. To prevent the collision on the transmission channel, our TDMA scheduling mechanism requires that every packet transmitted by any vehicle should contain additional information, called Frame Information (FI). The FI consists of a set of ID Fields (IDFs) of size equal to the number of time slots per frame, T . Each IDF is dedicated to the corresponding time slot of a frame. The basic FI structure is shown in Figure 4. Each time slot is dynamically reserved by an active vehicle (the vehicle whose communication device is working) for collision-free delivery of the safety messages or other control messages. The Node ID field contains the ID of the vehicle that is accessing this slot. Each vehicle is identified by its MAC address as well as an integer number. The Status field contains the status of each slot which indicates whether the slot is Idle, Busy or Collides. Finally, the Type field indicates the type of the packet transmitted by the corresponding vehicle, i.e. periodic information or event-driven safety messages.

B. TDMA slot scheduling mechanism

Our distributed TDMA scheduling mechanism uses the vehicular location information sufficiently to help the vehicles access the channel in an efficient way. As in VeMAC protocol, the channel time is partitioned into frames and each frame is further partitioned into two sets Lef t and Right. Furthermore, each half frame is partitioned into three sets of time slots S 0 , S 1 , and S 2 . These sets are associated with vehicles moving in the areas x i , x i+1 , and x i+2 , respectively. As shown in Figure 2, by dividing the time slots reserved for each direction into three sets, the vehicles v 1 and v 3 that are moving within the two areas x 1 and x 3 , respectively, can not transmit simultaneously to the vehicle v 2 because they are accessing disjoint sets of time slots. Therefore, our TDMA scheduling mechanism can decrease the rate of collision due the hidden node problem in VeMAC caused by node mobility. In each area, the vehicles access to the time slots associated to their locations and mobility direction with the same probability. In the next, we assume the following notations:

• S i (x):
The set of time slots associated to the direction and the area in which the vehicle x is traveling.

• N (x): The set of neighbors1 of vehicle x on the transmission channel.

Every active vehicle in the network should a fixed slot in the frame for safety messages or other control packets delivery. It is obvious that a vehicle's slot cannot be reused by any neighboring vehicles within the same area as well as in the adjacent areas, otherwise collisions will occur. The goal of this work is to propose an efficient slot reuse algorithm along the road without having to use expensive spectrum and complex wideband mechanisms such FDMA or CDMA. In fact, the three subsets of time slots will be reused between neighboring areas in such a way any vehicle in different adjacent areas access to the channel at the same time and thus no interference will occur. Suppose an active vehicle x needs to acquire a time slot on the transmission channel. The vehicle x starts listening to the channel during the set of time slots reserved for its direction and for its area in which is traveling, S i (x).

• Each vehicle that hears exactly one node transmission in a time slot reserved to its location and mobility direction, it will set the status of the slot to busy and record the ID of the vehicle accessing the channel at this time slot in the corresponding Node ID field.

• Each vehicle that receives multiple FIs from different vehicles during the same time slot, it will consider that the slot is occupied by more than one vehicle and sets its status as collide.

• If the vehicle does not hear anything during a specific time slot, it will set its status as free.

At the end of the frame, the vehicle x can determine the set N (x) and the set of busy slots in S i (x) used by each vehicle i ∈ N (x), denoted by P (x). In order to avoid any collision problem, this set of time slots are prohibited from being reused by any other vehicle in neighboring areas. Therefore, the vehicle x can determine the set of available time slots V (x) and then attempts to allocate one of them randomly, say time slot k.

Algorithm 1 outlines the details of the frame information formation. In the algorithm, i is the index of the area on which a vehicle is traveling. If no other vehicle is moving in the same area of vehicle x attempts to acquire a time slot k, then no access collision happens. In this case, the attempt of vehicle x is successful and all nodes i ∈ N (x) add vehicle x to their sets N (i) and record that vehicle x is using time slot k. However, if at least one node within the same area of vehicle x accesses Algorithm 1 FI formation Input S i (x) : the set of time slots that the vehicle x can reserve. α i , β i : are the index of the first and the last slot of the set S i (x), respectively.

1: for each slot index s = α i to β i do 2:

if only one vehicle j is heard in the slot s then if more than one vehicle are heard in the slot s then end if 12: end for time slot k, then all the transmissions fail and the time slot k is not acquired by any of the contending vehicles. In this case, the vehicle x will discover that its attempt was unsuccessful as soon as it receives a packet from any node i ∈ N (x) indicating that vehicle x / ∈ N (i). Vehicle x then re-accesses one of the time slots in V (x), and so on until all nodes i ∈ N (x) indicate that node x ∈ N (i) and announce the time slot accessed by vehicle x. However, when accessing collision happens among the vehicles that are moving in the same area, the probability of access collision in the next reservation is maximized since the choice of each colliding vehicle x will be limited in the new set V (x). In order to ensure channel access continuity, each vehicle should determine the expected available time slots on the set of time slots associated with the next area before leaving its current area in which is traveling. In fact, when a vehicle is using a given time slot in the set S i , it should allocate an available time slot on the set S (i+1)%3 as its future time slot before leaving its current area (i.e., dist x mod R ≈ 0), where dist x is the distance traveled by the vehicle x and R is the communication range. Algorithm 2 outlines the details of the slot reservation. It is executed by each vehicle which needs to reserve a time slot. Go back to 4 13: end if V. ACCESS COLLISION PROBABILITY AND THROUGHPUT ANALYSIS this section, the model of the average access collision probability and throughput are derived. In this work, we assume that the VANET scenario taken into account is a twoway highway of length equal to L. We assume that every area in the road has a unique index number such as 1, 2, . . . , N . The probability which the vehicle in the i -th area decides to access the available j -th time slot reserved for its direction and location is denoted by p ij . Such as the probability of the vehicle in the fourth area accessing the 7-th slot is denoted by p 47 . First of all, we calculate the access collision probability where a vehicle appears in every area tries to access an available time slot.

• A i : Actual number of active vehicles in a given area x i .

• T : Number of time slots.

• P aci : the access collision probability of the vehicle in area x i accessing channel.

• α i , β i : The indexes of the first and the last time slots reserved for the area x i .

The access collision probability of a vehicle in area A 1 can be founded as:

P ac1 = 1 -P nac1 (1)
P nac1 = β1 ∑ j=α1 p 1j * A1 ∏ k=2 (1 -p 1j ) (2)
where P ac1 denotes the access collision probability in area x 1 and in a given time slot, while P nac1 denotes the non-access collision probability in area x 1 and in a given time slot.

Based on the above derivation, the expression of total access collision probability of the vehicle in all locations can be given by:

P act = 1 -P nact ( 3
)
P nact = N ∑ i=1 P naci = N ∑ i=1 βi ∑ j=αi p ij * Ai ∏ k=2 (1 -p ij ) (4)
where, P act represents the total access collision probability of the vehicle in the studied highway accessing the channel, P nact represents the total non-access collision probability of the vehicle in the studied highway accessing the channel.

P aver-ac = 1 T * P nact (5)
P aver-ac represents the average access collision probability of the vehicle in the studied highway accessing the channel.

The throughput estimated by the average rate of messages successfully transmitted over the channel. The average throughput is obtained by: T H aver = C T * P nact [START_REF] Uzcátegui | Wave: A tutorial[END_REF] where, T H aver denotes the average throughput, C denotes the total channel capacity of the bandwidth.

VI. DTMAC QOS OPTIMIZATION

The channel time is partitioned into frames and each frame is divided into T slots. Moreover, the road is dissected into N small fixed areas. This means that, there may exist access collision when multiple vehicles try to access to the same time slot at the same time. We are motivated to design an optimal TDMA based MAC protocol with minimal access collision probability and high throughput. According to ( 4) and ( 6), we can note that the access collision probability and the throughput are dependent on the input parameters of DTMAC (i.e., T, N, α i and β i ). We are motivated to optimize the parameters of DTMAC to design an optimal TDMA based MAC protocol with minimal access collision probability and high throughput. Therefore, the DTMAC QoS optimization can be formulated as multi-objective optimization problem whose inputs are the DTMACs parameters and whose objectives are: Reducing the access collision probability, and maximizing the throughput;

The objective functions and the constraint conditions of the optimization problem can be written as:

(1) Objective functions: (2) Constraint conditions:

(s.t.)

         βi ∑ j=αi p ij = 1 ∀ i = 1 . . . N 0 ≤ p ij ≤ 1 ∀ i = 1 . . . N, ∀ j ∈ [α i , β i ] α i < β i < T ∀ i = 1 . . . N

VII. CONCLUSION

The Design of efficient TDMA based MAC protocols is an important issue in VANETs due to the rapid changes in network topology and the lack of infrastructure. In this paper, we propose a completely distributed and infrastructure free TDMA scheduling scheme, named DTMAC which exploits the linear feature of topology in VANET The ways that slots are scheduled and reused between vehicles are designed to avoid the transmission collision caused by the hidden node problem. Analytical models of the average access collision probability and throughput are proposed. Moreover, the parameters tuning of DTMAC is formulated as a multiobjective optimization problem in order to find the optimal parameters that optimize the QoS of DTMAC protocol in terms of access collision and throughput. In our future work, we will evaluate the performance of DTMAC in realistic VANET mobility scenarios by using SUMO/MOVE and ns2 and we will provide simulations results and analysis. Moreover, we plan to compare the simulation results founded by ns2 with those that will be founded by the analytical model.

Fig. 1 .

 1 Fig. 1. Merging collision problem.

Fig. 2 .

 2 Fig. 2. The partition of the studied highway into N areas.

Fig. 3 .

 3 Fig. 3. TDMA slots scheduling principle.

Fig. 4 .

 4 Fig. 4. Frame Information (FI) structure.

7 :F

 7 I[s].Status ← Collide 8: else // Anything is heard in the slot s 9: F I[s].Status ← F ree 10:

First objective:( 1 -

 1 minimizing the access collision probabilityP act = 1 -p ij )Second objective: maximizing the average throughputT H aver = C T * P nact

  Algorithm 2 Slot reservation 1: Determine driving direction and area x i . 2: Determine the set of time slots S i associated with the areax i . 3: Determine the available time slots V . 4: if V ̸ = {⊘} then

	5:	Randomly reserve an available time slot k.
	6: end if
	7: if All the received FIs in the next frame indicate that the
		slot k has been reserved by the vehicle x then
	8:	Successf ul ← 1
	9: else // There is other vehicle within its area x i reserving
		the same slot k
	10:	Successf ul ← 0
	11:	Release the time slot k
	12:

The set of neighbors is the set of vehicles that are moving within the same area.