This Deliverable Report describes the research performed within Work Package 3, Task 3.1 (Control Subject to Transmission Constraints, no Transmission Errors), in the first 35 months of the project. It targets the issue of control subject to transmission constraints with no transmission error.

This research concerns problems arising from the presence of a communication channel (specified and modeled at the physical layer) within the control loop. The resulting constraints include finite capacities in the transmission of the sensor and/or actuator signals. Our focus is on designing new quantization, compression and coding techniques to support networked control in this scenario.

A first contribution of this report is a new adaptive differential coding algorithm for systems controlled through a digital noiseless channel with limited channel rate. The proposed technique results in global stability for noiseless MIMO systems, with a data-rate which is known to be the minimal required (as assessed by information-theoretical limits known in the literature as 'data-rate theorem'). With respect to existing algorithms, our scheme improves the transient behavior.

A second line of research for the noiseless scenario has addressed the effect of limited data-rate in an algorithm running over a network. As a representative example, the consensus algorithm has been analyzed, and in particular its randomized version known as gossip algorithm. Static quantizers have been considered at first (both deterministic and probabilistic) and then the dynamic adaptive quantizers have been introduced also in this setting.

Introduction

Control and communications traditionally were two separate research areas, with almost no interaction, and the classical estimation and control theories were developed under the assumption that all data transmission required by the algorithm could be performed instantaneously, without errors and at an infinite data-rate. This simplified approach works well for engineering systems with only one plant and one controller, and where communication happens through a short wired connection, allowing a large bandwidth use. However, in the last two decades, the flaws of such a simple approach have been highlighted by a number of new technological applications, where the plant and the controller are not spatially adjacent, and communicate using different kinds of transmission media, e.g. wireless transmission, or exchange of packets through the Internet; even more challenging is the case when multiple sensors and multiple controllers must communicate in order to achieve a common goal, without centralized supervision.

The problem of remotely controlling dynamical systems over communication channels has gained significant attention in recent years. Such problems ask for interaction between stochastic control theory and information theory [START_REF] Bansal | Simultaneous design of measurement and control strategies for stochastic systems with feedback[END_REF][START_REF] Farhadi | LQG optimality and separation principle for general discrete time partially observed stochastic systems over finite capacity communication channels[END_REF][START_REF] Farhadi | Robust coding for a class of sources: applications in control and reliable communication over limited capacity channels[END_REF][START_REF] Farhadi | Stability and reliable data recosntruction of uncertain dynamic systems over finite capacity channels[END_REF]. The recent research area known as networked control takes into account the issues arising from communication: delays, limited data-rate and transmission errors or packet losses. In this report we focus on the effects of a limited data-rate.

For the limited data-rate, a fundamental set of results in the literature, which goes under the name of data-rate theorem ( [START_REF] Nair | Mean square stabilisability of stochastic linear systems with data rate constraints[END_REF][START_REF]Stabilizability of stochastic linear systems with finite feedback data rates[END_REF], also see the survey [START_REF] Nair | Feedback control under data rate constrints: An overview[END_REF] and the references therein), concerns the stabilization of a LTI system under different assumptions on the plant noise, and with the assumption that the communication channel is noiseless. It has been established that the stabilization is possible if and only if the data rate allowed to flow at each channel use is larger than the entropy of the plant, defined as λ max(log 2 |λ|, 0) bits, where the sum is over the eigenvalues of the plant's update matrix. The intuition is that the fastest is the instability evolution, the more bits are needed in order to learn where the state is going. The proof of the achievability of stabilization at any rate above the plant's entropy is based on adaptive quantization schemes that require both encoder and decoder to have some memory and to maintain a common state (zoom-in/zoomout quantizer, adaptive delta-modulation). In this report (section 2), we propose a variation on such a scheme, which introduces also a dwell-time in between zoomin and zoom-out phases. Our algorithm provides robustness against disturbances and improves the transient behavior.

We also address the issues arising from limited data rate in a more complex scenario, where not only one plant and one controller need to communicate, but a whole sensor and actuator network is present. Reliable transmission of information among the nodes of a network is known to be a relevant problem in information engineering. It is indeed fundamental both when the network is designed for pure information transmission, as well as in scenarios in which the network is deputed to accomplish some specific tasks requiring information exchange. Important examples include: networks of processors performing parallel and distributed computation [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF][START_REF] Tsitsiklis | Problems in decentralized decision making and computation[END_REF], or load balancing [START_REF] Cybenko | Dynamic load balancing for distributed memory multiprocessors[END_REF][START_REF] Diekmann | Efficient schemes for nearest neighbor load balancing[END_REF][START_REF] Muthukrishnan | First and second order diffusive methods for rapid, coarse, distributed load balancing[END_REF]; wireless sensor networks, in which the final goal is estimation and decision making from distributed measurements [START_REF] Intanagonwiwat | Directed diffusion: a scalable and robust communication paradigm for sensor networks[END_REF][START_REF] Kempe | Gossip-based computation of aggregate information[END_REF][START_REF] Zhao | Computing aggregates for monitoring wireless sensor networks[END_REF][START_REF] Dimakis | Geographic Gossip: Efficient Averaging for Sensor Networks[END_REF]; sensors/actuators networks, such as mobile multi-agent networks, in which the final goal is control [START_REF] Jadbabaie | Coordination of groups of mobile autonomous agents using nearest neighbor rules[END_REF][START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF][START_REF] Moreau | Stability of multiagent systems with time-dependent communication links[END_REF][START_REF] Ren | Consensus seeking in multiagent systems under dynamically changing interaction topologies[END_REF].

As a first step towards the challenging goal of understanding in-network es-timation and control, we focus on a simple but significant distributed algorithm: consensus algorithm (see e.g. [START_REF] Jadbabaie | Coordination of groups of mobile autonomous agents using nearest neighbor rules[END_REF][START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF][START_REF] Moreau | Stability of multiagent systems with time-dependent communication links[END_REF]). In particular, we consider here a randomized version of consensus, known as 'gossip algorithm' (see [START_REF] Boyd | Randomized gossip algorithms[END_REF]), and we present in section 3 the study of how quantization affects its performance, and the construction of quantization coding schemes which allow to achieve good performance. We present at first static quantizers, both deterministic and probabilistic, and then we study adaptive (zoom-in zoom-out) schemes.

2 Dwell-Time adaptive Delta modulation signal coding for networked controlled systems

Main idea

This section deals with the problem of control with limited data rates in the area of Networked Controlled Systems (NCS). Limited data rates impose a trade off between the communication bandwidth and the amount of requested information for stabilization. Large quantization errors and instability of the system may be observed when this trade off is not done properly (in particular for open-loop unstable systems). The objective of our work is then to look for a new adaptive quantization algorithms that reaches global stability with smooth transient behavior for MIMO systems, while minimizing the number of required bits.

In this section, we propose a new adaptive differential coding algorithm for MIMO systems, with exponential stability with improved transient behavior. Adaptive differential coding combines the advantages of differential coding, i.e., minimum bits representation, and adaptive coding, i.e., good stability performance. The algorithm reaches the rate theoretical limits (the algorithm is coded with the minimum number of possible bits under fixed-length coding) and results in global stability. In the new adaptive differential coding strategy, we introduce a new Dwell-Time state in addition of Zoom-In and Zoom-Out classical states. This allows a better estimate of the transition condition between Zoom-In and Zoom-Out states, and thereby its transition improves the global behavior of the algorithm. In fact, the Dwell-Time mechanism introduces a hysteretic effect that smoothes out the periodic and oscillatory behavior observed in other adaptive coding strategies, such as [START_REF] Sharon | Input to state stabilization with number of quantization regions[END_REF], and [START_REF] Nesic | Input to state stabilization of linear systems with quantized state measurements[END_REF]. During Dwell-Time state, past coded information is collected and kept in memory during a finite time. This information is used to predict the moment when the reconstructed state error leaves a threshold indicating to which state (Zoom-In, or Zoom-Out) the transition should be enabled. Because of this behavior the algorithm is named Dwell-Time Zoom-In/Zoom-Out (D-ZIZO).

Problem formulation

The following conventions will be used throughout the paper:

• N denotes the set of positive integers.

• I m denotes the identity matrix of dimension m × m.

• T s is the sampling period.

• n is the state dimension that corresponds to the number of sensors,

• m is the number of control inputs,

• x(k) = [x 1 (k), . . . , x n (k)] T ∈ R (n×1)
is the n-dimensional state vector at instant kT s (each x i (k) corresponds to the ith sensor) ; m×1) , is the m-dimensional control input vector at instant kT s .

• u(k) = [u 1 (k), . . . , u m (k)] T ∈ R (
• A is the open-loop matrix and B is the matrix associated to the control inputs with A ∈ R (n×n) and B ∈ R (n×m) . The pair (A, B) is controllable.

• x(k) is an estimation of x(k) and, more generally, for a given signal s(k), ŝ(k) represents an estimated value of s(k).

• x(k) denotes the estimation error:

x(k) = x(k) -x(k), and s(k) represents the error s(k) -ŝ(k).
The problem considered is the stabilization of a multivariable system, in which sensor signals are centralized, and then transmitted through a digital noiseless communication link to a remote controller.

The discretized system is given by:

x(k + 1) = Ax(k) + Bu(k) (1)
The controller law is given by:

u(k) = -K x(k) (2)
T (k) Adaptive quantization law ∆(k) δ(k) encoder z(k) x(k) System Quantizer + x(k) - T -1 (k)

Model based predictor

Model based predictor with K ∈ R (n×m) such that the matrix A -BK is Schur (the module of A -BK's eigenvalues are strictly inferior than 1).

u(k) ∆(k) T (k) x(k) ẑ(k) x(k) δ(k) Linear state feedback Quantization step reconstruction ∆(k) δ(k) decoder δ(k) ẑ(k) x(k) x(k) Transmission channel
Fig. 1 illustrates the general architecture of the proposed differential adaptive coding algorithm. It is composed of four main blocks, as described below:

1. The rotation matrix T (k) which transforms the estimation error

x(k) = [x 1 (k), . . . , xn (k)] T into a new set of coordinates z(k) = [z 1 (k), . . . , zn (k)] T .
The aim of this matrix is to reduce the complexity of the analysis and design (originally in dimension n) to a set of several independent subsystems with smaller dimension than the original system. Specific details on the construction of this matrix will be given latter in section 2.3.1.

2.

The vector quantizer block which transforms the error z(k) , using the adaptive quantization steps

∆(k) = [∆ 1 (k), . . . , ∆ n (k)] T to the codeword δ(k) = δ(z(k)) = [δ 1 (k), . . . , δ n (k)
] T , by using the following map:

δ i (k) =      (M i -1)/2 if C + , holds N j if C j , holds -(M i -1)/2 if C -, holds (3)
with where the set of conditions C j are defined as follows:

N j = M i -j 2 , ∀j = 3, 5, 7, 9, . . . , (2M i -3) z(k) δ(k) - 1
1 -∆(k) 2 ∆(k) 2
C + : zi (k) ≥ (M i -2)∆ i (k)/2 C j : (N j -1/2)∆ i (k) ≤ zi (k) < (N j + 1/2)∆ i (k), C -: zi (k) < -(M i -2)∆ i (k)/2
Fig. 2 illustrates the quantization policy for the scalar case using 3 words per signal.

3.

Adaptive quantization law which maps the codeword δ(k), to the adaptive quantization steps ∆(k). The precise equations and the associated stability properties will be detailed in section 2.3. The adaptation law will be of the following general form:

∆(k + 1) = Φ(∆(k), δ(k), ..., δ(k -ν + 1)), (4)
where ν is the size of the adaptation law window, which will be related to the system eigenvalue structure (i.e. the number of similar poles, etc.). It will be also directly related to the Dwell-Time state defined for our proposed algorithm.

4.

The model based predictor which transforms back the codeword, δ(k), to the system state estimation x(k), by using the following predictor equation:

x(k + 1) = (A -BK)x(k) + AT (k) ẑ(k) (5)
with

ẑ(k) = [ ẑ1 (k), . . . , ẑn (k)] T , where ẑi (k) = ∆ i (k) • δ i (k), 1 ≤ i ≤ n.
In the following sections, we attempt to find a suitable function Φ, in (4) under which the closed-loop system is globally stable with smooth transient behavior and reaches the rate theoretical limits under constant length coding.

The D-ZIZO algorithm for multivariable systems

The D-ZIZO algorithm for scalar systems with M = 3 was introduced in [START_REF] Gomez-Estern | Dwell-time adaptive Delta modulation signal coding for networked control systems[END_REF]. In this section we generalize it to the case of multivariable systems with arbitrary quantization levels. The main ideas for this extension involve:

• Using a transformation matrix T (k) (section 2.3.1), which reduces the complexity of the analysis and design to a set of several independent subsystems with smaller dimension.

• Suitably initializing the quantization steps ∆ i (0)

• Extending the results of [START_REF] Gomez-Estern | Dwell-time adaptive Delta modulation signal coding for networked control systems[END_REF] to a system with µ number of quantization levels per signal.

• Defining a condition C T to switch from Dwell -Time (DT) to Zoom -Out (ZO) in the case that unexpected time-limited disturbances cause quantizer overload. If condition C T does not hold, Zoom-In (ZI) always occurs after Dwell-Time.

The value of the Dwell-Time period ν will chosen such that it provides enough samples to form a robust criterion (i.e., C T ) to decide to switch ZO mode only if strictly necessary.

• As in the scalar case [START_REF] Gomez-Estern | Dwell-time adaptive Delta modulation signal coding for networked control systems[END_REF], the stability analysis will be based on the dynamics of the error-to-quantizer ratio, which for multivariable systems is defined as follows,

y(k) . = [z 1 (k)/∆ 1 (k), z2 (k)/∆ 2 (k), . . . zn (k)/∆ n (k)] T .

The rotation matrix T (k)

As explained before the aim of the rotational matrix T (k) is to reduce the complexity of the analysis and design to a set of subsystems with smaller dimension. This transformation is obtained by a) Applying the real Jordan canonical transformation (Lemma 1) and b) A transformation that transforms the Jordan blocks associated with complex conjugate eigenvalues to a form similar to the Jordan block associated with the real valued eigenvalues (Lemma 2).

Lemma 1. [START_REF] Hirsch | Differential Equations, Dynamical Systems, and Linear Algebra[END_REF] For A ∈ R n×n there exists a real valued nonsingular matrix Φ and a real valued matrix Γ such that ΦAΦ -1 = Γ = diag(J λ 1 , . . . , J λγ ), where for the multi-valued real eigenvalue λ l with multiplicity µ l , the matrix J λ l , for 1 ≤ l ≤ α ≤ γ, are of the following form:

J λ l =       λ 1 1 λ l 1 . . . λ l       = F (λ l ) ∈ R µ l ×µ l . ( 6
)
And for the multi-valued complex conjugate eigenvalues λ l = |λ l |(cos(θ l ) ∓ sin(θ l )) with multiplicity µ l , the matrix J λ l , are, for all α + 1 ≤ l ≤ γ, of the form

J λ l =       |λ l |R(θ l ) I 2 |λ l |R(θ l ) I 2 . . . |λ l |R(θ l )       ∈ R 2µ l ×2µ l , ( 7
)
where R(θ l ) is the rotation matrix given by

R(θ l ) = cos(θ l ) sin(θ l ) -sin(θ l ) cos(θ l ) . ( 8
)
Above lemma implies that we can always express the system matrix A of the system (1) in its real Jordan form. That is, A can be written in the form of A = diag(J λ 1 , . . . , J λγ ). Thus, without loss of generality, we assume that A = diag(J λ 1 , . . . , J λγ ). For the simplicity of analysis, it is desirable to transform the Jordan blocks associated with complex conjugate eigenvalues to a form similar to the case of real valued eigenvalues. For the multi-valued complex conjugate eigenvalues, we introduce a change of coordinate with a dynamic matrix T (k) to transform the associated Jordan block to a form similar to [START_REF] Carli | Average consensus on networks with transmission noise or quantization[END_REF]. This transformation is discussed in the following lemma. Lemma 2. [START_REF] Jaglin | Dwell -time adaptive delta modulation signal coding for networked controlled systems[END_REF] Consider the Jordan block J λ l which corresponds to the complex conjugate eigenvalues λ l = |λ l |(cos(θ l ) ∓ sin(θ l )) with multiplicity µ l . Let us introduce matrices W (θ l ) ∈ R 2µ l ×2µ l and Q(θ l ) ∈ R 2µ l ×2µ l as follows:

W (θ l ) =       R(θ l ) R(θ l ) . . . R(θ l )       , Q(θ l ) =       R(θ l ) R(2θ l ) . . . R(µ l θ l )       . ( 9
)
Then, under the transformation

z(k) = T -1 (k)x(k), T (k) = W (kθ l )Q(θ l )
, we have a similar form as in the case of real valued eigenvalues.

The change of coordinates with a dynamic matrix T (k) allows us to reduce the study to the following class of systems:

z(k + 1) =       |λ l | 1 |λ l | 1 . . . |λ l |       F (|λ l |)∈R µ * µ (z(k) -ẑ(k)). (10)
For the simplicity of presentation from now on let λ l = λ and µ l = µ. From above lemmas it follows that the change of coordinates allows us to reduce the study to the following class of systems:

z(k + 1) =       λ 1 λ 1 . . . λ       F (λ)∈R µ * µ (z(k) -ẑ(k))
for real valued eigenvalues; and

z(k + 1) =       |λ| 1 |λ| 1 . . . |λ|       F (|λ|)∈R µ * µ (z(k) -ẑ(k))
for complex conjugate eigenvalues. For these systems let the vector y(k) include components

y i (k) = zi (k)/∆ i (k) (1 ≤ i ≤ µ) and let D(k) = diag(∆ i (k))
where ∆ i (k)'s are the quantization steps. Then, we obtain the following error equation:

y(k + 1) = G(λ)(y(k) -δ(k)), (11)
where:

• for real valued eigenvalues:

G(λ) = G r (λ) = D -1 (k + 1)F (λ)D(k) =         λ∆ 1 (k) ∆ 1 (k+1) ∆ 2 (k) ∆ 1 (k+1) λ∆ 2 (k) ∆ 2 (k+1) ∆ 3 (k) ∆ 2 (k+1) . . . λ∆µ(k) ∆µ(k+1)        
, and

• for complex conjugate eigenvalues:

G(λ) = G c (|λ|) = D -1 (k + 1)F (|λ|)D(k) =         |λ|∆ 1 (k) ∆ 1 (k+1) ∆ 2 (k) ∆ 1 (k+1) |λ|∆ 2 (k) ∆ 2 (k+1) ∆ 3 (k) ∆ 2 (k+1) . . . |λ|∆µ(k) ∆µ(k+1)         .

Further definitions for the D-ZIZO algorithm

Starting from the previous matrices, some definitions and arrangements will be instrumental for the algorithm specification and analysis. First, we will benefit from the previous variable change to consider every subsystem derived from and eigenvalue of multiplicity µ, (2µ if complex conjugate) as a unique system evolving independently of the rest (two systems in the case of complex conjugate pairs), with their own (F (|λ|, G(λ)). For a µ-dimensional system of that type, consider the vector of quantization steps,

∆(k) = [∆ 1 (k), ∆ 2 (k), . . . , ∆ µ (k)] T .
As the initial state estimation error is a freely assigned quantity for all variables, it might be appealing to choose all ∆ i (0) equal; however, as it will be shown later, this would have a negative effect on the transient performance as the errors propagate from one signal to the next in a cascade, due to the upper triangular structure of matrix F (|λ|). Subsequent calculations will show that an homogeneous ∆(0) would also impose suboptimal bandwidth assignment (via M ). A choice that does not add conservativeness to our results while it still guarantees a tractable analysis is the following

∆(0) = ∆ 1 (0) • [1, κ, κ 2 , . . . , κ µ ]
where ∆ 1 (0) > 0 and 0 < κ < 1 are freely chosen scalars. From the fact that the ZO-ZI-DT machine state is unique (not element-wise), and assuming that C out and C in are the same for all element i of the state vector, we have that this proportion will hold along time, yielding the following simple matrices

G(λ) = 1 C m          |λ| κ 0 . . . 0 0 |λ| κ . . . 0 . . . 0 0 0 . . . κ 0 0 0 . . . |λ|          D(k) = ∆ 1 (k) • diag(1, κ, κ 2 , . . . , κ µ )
where C m stands for the Zoom factor corresponding to the current mode of operation, namely C out , 1 or C in for the respective ZO, DT and ZI modes. Under this assumption, it is clear that the ||G(λ)|| ∞ = (|λ| + κ)/C m which can be made arbitrarily close to |λ|/C m . The main consequence is that the rate-condition for stability of the algorithm can be minimized with the appropriate choice of κ, as it will be shown in the subsequent analysis. From the previous definitions, it is also convenient to define the following, Definition 1. The error-dynamics norm is defined as

ρ(k) = ||G r (λ)|| ∞ = ||G c (|λ|)|| ∞ ,
which, using the fact that the zoom factor is unique for all states anytime, and with the above choice of ∆(k), turns into

ρ(k) =      max 1≤i≤µ (|λ| + κ)/C out < 1(∆ µ+1 (0) = 0) if ZO max 1≤i≤µ {|λ| + κ} if DT max 1≤i≤µ (|λ| + κ)/C in > 1 if ZI (12)
From Lemma 1, Lemma 2 and the above results it follows that for the stability analysis, it is enough to focus only on the error equation [START_REF] Dimakis | Geographic Gossip: Efficient Averaging for Sensor Networks[END_REF]. Note that for |λ| < 1, lim k→∞ z(k) = 0. Consequently, in what follows, without loss of generality, we assume that |λ| > 1.

Description of the D-ZIZO

Definition 2. The stability analysis and the full description of the complete D-ZIZO algorithm, requires the following set definitions:

B o = {y(k) : 1 ≤ i ≤ µ : |y i (k)| ≤ (M i -2) 2 } B ext = {y(k) : 1 ≤ i ≤ µ : |y i (k)| ≤ M i 2 } B int = {y ∈ R µ : |y i | ≤ |λ| + κ 2C in ∀i : 1 ≤ i ≤ µ -1 and |y µ | ≤ |λ| 2C in } B u = {- min 1≤i≤µ M i -m 2 , ..., min 1≤i≤µ M i -m 2 , m = 3, 5, ..., min 1≤i≤µ M i }
The operation of the adaptive quantization multivariable D-ZIZO law is described by Fig. 3. The algorithm switches between the following states:

• "Zoom-Out" state activates the capture mode where ∆(k) increases with a rate ∆(k + 1) = C out ∆(k), where C out > 1. The precise value of C out , given later, will depend on the initial condition of ∆(0) and on the system matrix A. Then, by monitoring δ(k) the algorithm will switch to Zoom-In mode, and hence y(k) → B o ⊂ B ext , in finite time.

• "Zoom-In" state makes ∆(k) decrease with a rate

∆(k + 1) = C in ∆(k), where C in < 1.
The precise value of C in , given later, will depend on the initial condition of ∆(0) and on the system matrix A. Then, by monitoring δ(k) the algorithm will switch to Dwell-Time mode.

• "Dwell-Time" state freezes the evolution of ∆(k). That is, ∆(k + 1) = ∆(k). Let k DT be the time when the algorithm enters in Dwell-Time state.

Using the information collected during the time period of

[k DT , k DT +ν -1],
the algorithm is able to determine whether y(k DT ) ∈ B ext ; or y(k DT ) / ∈ B ext . Then, the algorithm backs to "Zoom-In" mode if

y(k DT ) ∈ B ext . ZOOM IN DWELL TIME ZOOM OUT ∆(k + 1) = ∆(k) ∆(k + 1) = Cout∆(k) ∆(k + 1) = Cin∆(k)
CT false after ν samples Otherwise; if y(k DT ) / ∈ B ext , then the algorithm moves to "Zoom-Out" mode. The duration in Dwell-Time mode is finite and bounded by a parameter ν which depends only on the open loop system eigenvalues, the number of words (M 1 , ..., M µ ) and the initial values of the quantization steps (∆ 1 (0), ..., ∆ µ (0)).

δ(k) ∈ B u k < kDT + ν δ(k) ∈ B u δ(k) / ∈ B u CT true δ(k) / ∈ B u

Stability analysis

The stability of D-ZIZO can be analyzed throughout the following steps:

• Capture and transition from Zoom-Out to Zoom-In (Lemma 3),

• Invariance property of B ext during Zoom-In mode (Lemma 4),

• Transition from Zoom-In to Dwell-Time (Lemma 5),

• Definition of the transition condition C T (Lemma 6)

• Stability of the closed-loop system (Theorem 1).

Standard mode transitions

We start this section with the following lemma, which shows that if the algorithm is initialized in Zoom-Out mode, then there exists a finite time k catch , at which the algorithm switches to Zoom-In mode. Note that for M i ≥ 3, the condition for switching is that δ(k catch ) ∈ B u ; and for M i = 2, the condition is that the sign of each components of vector δ(k catch ) has been changed.

Lemma 3 (Capture and Transition from ZO to ZI). Assume that initially, the algorithm is in Zoom-Out mode, and let the initial values of the quantization steps be constrained by

|λ| + κ ≤ M i , 1 ≤ i ≤ µ, ∆ µ+1 (0) = 0, ∆ 1 (0) = 0, 1 ≤ i ≤ µ. ( 13
)
And

C out > 0 satisfies max 1≤i≤µ (|λ| + κ) < C out . ( 14
)
Then, there exists a finite time, k catch > 0, after which the algorithm reaches in Zoom-In mode. That is, for any bounded value of y(0), we have:

y(k catch ) ∈ B o ⊂ B ext , ∀M i ≥ 3, y(k catch ) ∈ B ext , M i = 2.
or, equivalently y(k catch ) ∈ B ext , ∀M i ≥ 2.

Proof: The analysis is done for two separate cases: M i ≥ 3 and M i = 2. The complete proof for both cases is based on establishing a contraction mapping. The complete proof is given in [START_REF] Jaglin | Dwell -time adaptive delta modulation signal coding for networked controlled systems[END_REF].

Remark 1. It is interesting to note that the bigger C out is, the faster the signal is caught. However, taking a big value for C out implies a big value for ∆(k). This results in a larger excursion of the solution of y(k) from its equilibrium. Now, we show that if the algorithm is in Zoom-In mode, at some time k, i.e.,

y(k) ∈ B ext , then y(k + 1) ∈ B ext , at time k + 1.
Lemma 4 (Invariance of B ext during Zoom-In mode). Assume that the algorithm is in Zoom-In mode with y(k) ∈ B ext , and that the initial values of ∆(0) and the number of words M i is constrained by the inequality (13), with C in > 0 satisfying

max 1≤i≤µ |λ| + κ M i < C in < 1. (15)
Then, y(k + 1) ∈ B ext .

According to [START_REF] Dimakis | Geographic Gossip: Efficient Averaging for Sensor Networks[END_REF] and ( 12), the error equation in Zoom-In mode gives:

y i (k + 1) = |λ| C in (y i (k) -δ i (k)) + κ C in (y i+1 (k) -δ i+1 (k)). ( 16
)
y µ (k + 1) = |λ| C in (y µ (k) -δ µ (k)). (17)
With

y(k) ∈ B ext we have |y i (k) -δ i (k)| ≤ 1 2 .
Then, using [START_REF]Average consensus on networks with quantized communication[END_REF], for 1 ≤ i ≤ µ, we get

|y i (k+1)| ≤ |λ| C in |y i (k)-δ i (k)|+ κ C in |y i+1 (k)-δ i+1 (k)| ≤ |λ| 2C in + κ 2C in ≤ M i 2 . ( 18
)
Also, from ( 17) and ( 15) it follows that

|y µ (k + 1)| ≤ M µ 2 . ( 19
)
That is, y(k + 1) ∈ B int with B int as defined before. From condition [START_REF] Frasca | Average consensus by gossip algorithms with quantized communication[END_REF], it follows that B int ⊆ B ext ; and therefore, together with the constraint on the value of C in , we have that y(k + 1) ∈ B ext . Now, in the following lemma we show that transitions from Zoom-In mode to Dwell-Time mode preserves invariance property of B ext . We next analyze the transition condition C T . Towards this goal, let k DT be the time instant when the state machine enters to Dwell-Time state from Zoom-In mode; and define the condition C T as follows:

C T = true if{k = k DT + ν -1} ∧ {∃i, 1 ≤ i ≤ µ : | k j=k-ν+1 δ i (j)| = M i -1 2 ν}
Transitions from Dwell-Time to either Zoom-Out, or Zoom-In depend on the condition C T . In the following lemma, we investigate the cases where this transition conditions are satisfied. Lemma 6 (Transition condition C T ). Suppose that we have the inequality 1 < |λ| < M i , and also that κ is chosen sufficiently small such that:

|λ| + κ < M i , 1 ≤ i ≤ µ. ( 20
)
Also, suppose that the duration of the Dwell -Time ν satisfies

ν = max(ν i ), (ν i -1) ∈ N ≥ l i
where

l i = ln M i + |λ| -2 -κ ln(|λ|) - ln M i -|λ| -κ ln(|λ|) . ( 21
)
Then, we obtain the following condition:

C T ⇒ y(k DT ) / ∈ B ext . ( 22
)
Proof: It follows from an induction argument. The complete proof is given in [START_REF] Jaglin | Dwell -time adaptive delta modulation signal coding for networked controlled systems[END_REF].

In normal operation, there is a continuous transition between ZI and DT modes which results in a contraction of the estimation error z(k). From Lemma 4 it follows that when the algorithm enters to ZI mode at time k catch , y(k) remains in B ext for all k ≥ k catch . If δ(k catch + 1) ∈ B u , the algorithm stays in ZI mode; otherwise, it switches to DT mode. But, because of the invariance property of B ext during ZI mode, we have y(k DT ) ∈ B ext .

Finally, condition of Lemma 6, can be used to detect abnormal situations where, due to some unmodelled disturbances, y(k DT ) leaves B ext . In those situations, the algorithm needs to switch to ZO mode. This procedure is described next.

Transition to ZO due perturbations

Starting from ZI mode, the event δ(k) / ∈ B u triggers the DT mode. In order to check condition C T , the system must remain in DT for at least ν samples, unless we have some k during that period such that |δ i (k)| < M i -1 2 for all i (which would mean that the system has returned to B u and the ZI is activated). If this is not the case, we would remain at DT until the ν samples have ellapsed, and then, condition C T would be evaluated for all components, with the following decision map:

• If C holds, a perturbation has occurred and ZO mode should be activated.

• Otherwise, switch to ZI.

Recoding for disambiguation

In order to consider all possible cases, a slight fix must be done to the coding algorithm. In fact, ( 22) is a one-way implication, and it might happen that C T is false and still y(k DT ) / ∈ B ext . So, even without fulfilling C T we must be able to detect the quantizer overload and switch to ZO mode. This is tackled by using the fact that the sender (encoder) can directly detect from the measures that y i (k DT ) / ∈ B ext for some i; in that case, even if the straight coding sequence should not result in C T , the sequence of δ i (k) transmitted during Dwell-Time should be transformed for it to fulfill the condition

| k j=k-ν+1 δ i (j)| = M i -1 2 ν.
With that fix, the receiver will be properly aware that it should switch to ZO mode. Now, we are ready to show the global stability using the proposed algorithm. This is shown in the following theorem:

Main stability result Theorem 1. Let the number of words M i satisfy the inequality [START_REF] Jadbabaie | Coordination of groups of mobile autonomous agents using nearest neighbor rules[END_REF]. To build the algorithm, we must introduce two scalars C out , C in which are respectively constrained by [START_REF] Fagnani | Randomized consensus algorithms over large scale networks[END_REF] and [START_REF] Frasca | Average consensus by gossip algorithms with quantized communication[END_REF].

Then, for all initial conditions z(0),

• ∃k catch > 0 such that ∀k ≥ k catch , y(k) ∈ B ext
• z(k) converges to 0

• The system is globally stable and this can be realized under the condition on the channel rate R, given as follows:

n i=1,|λ i |>1 |λ i | < 2 R = n i=1,M i =0 M i . ( 23
)
The system is described by the equation

z(k) ∞ ≤ M i 2 C k-k catch ν+1 in ∆(k catch ) ∞ , C in < 1
Thus, z(k) converges to 0. Now, if a perturbation occurs such that the condition C T is activated (or explicitly coded at the sender), the algorithm leaves the DT mode, and then this process will start over following the condition of Lemma 6.

The D-ZIZO algorithm in the presence of noise

This far, the analysis has been based on the noiseless system model [START_REF] Aysal | Distributed average consensus using probabilistic quantization[END_REF]. In order to take into account additive disturbances entering the system and their effect on the stability of the D-ZIZO algorithm, the system and error equations will be rewritten as follows:

x(k + 1) = Ax(k) + Bu(k) + s(k) x(k + 1) = (A -BK)x(k) + A x(k) z(k + 1) = T -1 (k + 1)AT (k)(z(k) -ẑ(k)) + T -1 (k + 1)s(k)
where s(k) is the additive noise. Before entering the analysis, two situations must be distinguished: i) That of bounded input noise on the system, i.e. ||s(k)|| < S and ii) unbounded additive disturbances. The main difference, is that in i), an appropriate choice of the system parameters will guarantee that ZO mode will be executed at startup in order to catch the initial state, and it will not be triggered anytime later, while in ii), zoom out stages may be required at any time due to state deviations provoked by time-limited noise bursts. In that case, some conditions will be derived from these bursts such that the overall dynamics does not result in total loss of stability.

Bounded noise

The infinity norm of T (k) is bounded, and hence the bound on s(k) immediately implies that w(k) .

= T -1 (k + 1)s(k) is bounded as

||w(k)|| ∞ < W
and the error equation is rewritten as

z(k + 1) = F (|λ|)(z(k) -ẑ(k)) + w(k)
The analysis will be focused on the error-to-quantizer ratio as in previous sections, whose dynamics is

y(k + 1) = D -1 (k + 1)z(k + 1) = D -1 (k + 1)(F (|λ|)(z(k) -ẑ(k)) + w(k)) (24) = D -1 (k + 1)F (|λ|)D(k)(y(k) -δ(k)) + D -1 (k + 1)w(k) (25) = G(λ)(y(k) -δ(k)) + D -1 (k + 1)w(k) (26)
In the following sections we will assume that in the noisy case the D-ZIZO modes are DT, ZI, ZO as in the standard algorithm, and that the switching conditions are left unchanged.

Transition from ZO to ZI with noise

Assume that the systems starts in ZO mode. We will show that there is a finite time in which the systems switches to ZI by analyzing he evolution of y(k) along a Zoom-Out stage:

y(k + 1) = G(λ)(y(k) -δ(k)) + D -1 (k + 1)w(k) (27) y(k + 1) ∞ = G(λ) ∞ y(k) -δ(k) ∞ + D -1 (k + 1)w(k) ∞ ≤ |λ| + κ C out y(k) ∞ + W ∆ 1 (k)C out = |λ| + κ C out k+1 y(0) ∞ + W ∆ 1 (0)C k+1 out k j=0 (|λ| + κ) j = |λ| + κ C out k+1 y(0) ∞ + W ∆ 1 (0)C k+1 out 1 -(|λ| + κ) k+1 1 -|λ| -κ
Now by choosing C out > |λ| + κ we ensure that all elements in this expression tend to zero, and hence we conclude that after some time y(k + 1) enters B int and the algorithm enters the Zoom In mode.

Invariance of B ext in ZI mode

In order to check this property it will be assumed that the system has entered the Zoom In Stage with an initial value of ∆(k catch ). The time evolution of y(k) is described as

y(k + 1) = G(λ)(y(k) -δ(k)) + D -1 (k + 1)w(k) y i (k + 1) = 1 C in (|λ|(y i -δ i ) + κ(y i+1 -δ i+1 )) + w i (k) C in ∆(k) , ∀i = 1 . . . µ -1 y µ (k + 1) = 1 C in |λ|(y µ -δ µ ) + w µ (k) C in ∆(k) Now using the bound y(k) ∈ B ext ⇒ |y i (k) -δ i (k)| ≤ 1/2 we have |y i (k + 1)| ≤ 1 2C in |λ| + κ + 2 W κ µ ∆ 1 (k) , ∀i = 1 . . . µ
and the invariance of B ext is ensured by making |y i (k + 1)| < M i /2. This can be only attained if the latter expression is upper bounded, for which ∆ 1 (k) should be lower bounded, i.e. a lower limit must be set for the quantization step by constraining the Zoom In operation to ∆ 1 (k) ≥ ∆ min for all k. This is the price to be paid in terms of quantization resolution in the presence of noise, which is reasonable enough as the presence of noise eventually carry variations in the steady state, rendering infinite resolution impractical. With this analysis, the necessary data-rate condition can be stated regardless of the noise power as

|λ| < M i ∀i = 1 . . . µ
because if this condition is fulfilled, the following bound (from above)

|y i (k + 1)| ≤ 1 2C in |λ| + κ + 2 W κ µ ∆ min < M i 2 ∀i = 1 . . . µ ( 28
)
will be satisfied with the appropriate choice of C in , κ and ∆ min .

Invariance of B ext in DT mode

If the previous bound holds for C in < 1, it will consequently be true for C in = 1, which corresponds to the Dwell-Time mode of operation.

Condition for entering the ZO mode

This far we have proved that B ext is an invariant both in ZI and DT modes. The transition from DT to ZO mode will be triggered by quantizer saturation (|y i (k)| / ∈ B ext ) only in abnormal cases, for instance due to a temporary disturbance increase above the upper bound W or to a loss of estimator synchronization.

In order for the receiver to detect such event, a sequence of δ i (k) must be unambiguously related to its occurrence. As in the noiseless case, we will prove that in normal conditions

C T ⇒ y(k) / ∈ B ext
where the condition C T is defined as

C T = true if {k = k DT + ν -1} ∧    | k j=k-ν+1 δ(j)| = M -1 2 ν    which is equivalent to say that if y(k DT ) ∈ B ext , then ∀i (1 ≤ i ≤ µ), | k DT +ν-1 j=k DT δ i (j)| = M i -1
2 ν. We consider each component y i (k) separately and determine ν i -1 as follows:

(ν i -1) ∈ N > l i ν = max 1≤i≤µ ν i .
where each ν i corresponds to an upper bound of the maximal time such that the following conditions are verified:

y(k DT ) ∈ B ext (29) sgn(δ i (k DT )) • k DT +ν i -2 j=k DT δ i (j) = (ν i -1) M i -1 2 (30)
We will show that at

k DT + ν i -1, it is impossible to have sgn(δ i (k DT ))δ(k DT + ν i -1) = M i -1 2 which is equivalent to have sgn(δ i (k DT ))y i (k DT + ν i -1) > M i -2 2 .
Thus, in what follows, will we find conditions under which the inequality

sgn(δ i (k DT ))y i (k DT + ν i -1) ≤ M i -2 2
holds. For this, it will be assumed that equations ( 29) and ( 30) are verified along the period ∀j ∈

[k DT , k DT + ν -2].
From previous arguments, we know that if y(k DT ) ∈ B ext , then during all the Dwell -Time period, we have y

(j) ∈ B ext , ∀j ∈ [k DT , k DT + ν -2]
. Thus, we can conclude that |y i+1 (j) -δ i+1 (j)| ≤ 1/2. From this fact and the error equation considering noise [START_REF] Moreau | Stability of multiagent systems with time-dependent communication links[END_REF] it follows that:

sgn(δ i (k DT ))y i (k DT + ν i -1) ≤ |λ| ν i -1 |y i (k DT )| - M i -1 2 |λ| ν i -2 j=0 |λ| j + W ∆ i (k DT ) + κ 2 ν i -2 j=0 |λ| j .
And under the assumption |y i (k DT )| ≤ M i /2, and using the lower bound ∆ 1 (k) ≥ ∆ min proposed in the previous analysis for the noise case, we have that the sufficient condition for sgn

(δ i (k DT ))y i (k DT + ν i -1) ≤ (M i -2)/2 thus violating C T turns into |λ| ν i -1 M i 2 - M i -1 2 |λ| |λ| ν i -1 -1 |λ| -1 + |λ| ν i -1 -1 |λ| -1 W κ i ∆ min + κ 2 ≤ M i -2 2 ,
From the previous equation, by a direct calculation, it follows that

ν i = ν ∈ N ≥ 1 + ln 1 + |λ|+M i +2-κ-2W κ i ∆ min -κ M i -|λ|-κ-2W κ i ∆ min ln(|λ|) = 1 + ln 1 + 2(1+|λ|) M i -|λ|-κ-2W κ i ∆ min ln(|λ|) . ( 31
)
Note that to have above inequality, we need to assume that M i > |λ| + κ + 2W κ i ∆ min . with this choice, if y i (k DT ) ∈ B ext , it is impossible to have a ν-long sequence of δ i (k) fulfilling C T . However, the backwards implication y i (k DT ) / ∈ B ext ⇒ remains uncertain. The solution is again to recode the δ i (k) signals at the encoder side as C T whenever the event y i (k DT ) / ∈ B ext is detected (see section 2.3.4). With that fix, the ZO mode will be triggered and the system will recover from timelimited unbounded disturbances (i.e. after an unbounded disturbance or burst, sufficient time must elapse, possibly with W -bounded noise, in order to recover the ZI mode and approach the attainable limit set).

Consensus over noiseless digital channels

Consensus algorithm is a very efficient methodology for solving some distributed estimation and control problems as already mentioned in the Deliverables D02.01 Cooperative control and estimation algorithms (rel. 1), D02.03 -Communication network design (rel. 1), and D02.05 -Scalability and Complexity (rel. 1). Some work has been done in order to understand how the presence of digital noiseless channels affects the performance of this algorithm. Moreover, some work has been devoted to determining smart coding methods allowing a better use of the communication capabilities of the channel. These two problems are the subject of following section.

A first part of the section describes the contributions given by the paper [START_REF] Carli | Gossip consensus algorithms via quantized communication[END_REF]. In this paper a randomized variation of the consensus algorithm is considered, which is called gossip algorithm and which will be briefly described below (see [START_REF] Boyd | Randomized gossip algorithms[END_REF] for a more complete description). The main contribution in [START_REF] Carli | Gossip consensus algorithms via quantized communication[END_REF] are the study of gossip algorithm when a static quantizer is applied to all messages sent along the network; both deterministic and probabilistic quantizers are considered. Then, in [START_REF] Baldan | An efficient quantization algorithm for solving average-consensus problems[END_REF], dynamic quantizers are analyzed (zoom-in zoom-out schemes, similar to those described in section 2), and compared to the static case.

The gossip algorithm

Assume we are given an undirected graph G = (V, E), E ⊂ {(i, j) : i, j ∈ V }. At each time step, one edge (i, j) is randomly selected in E with probability W (i,j) such that (i,j) ∈ E W (i,j) = 1. Let W be the matrix with entries W ij = W (i,j) . The two agents connected by that edge average their states according to

x i (t + 1) = 1 2 x i (t) + 1 2
x j (t)

x j (t + 1) = 1 2 x j (t) + 1 2 x i (t) (32)
while

x h (t + 1) = x h (t) if h = i, j. ( 33
)
Let E ij = (e i -e j )(e i -e j ) * and

P (t) = I - 1 2 E ij
where e i = [0, . . . , 0, 1, 0, . . . , 0] * is a N × 1 unit vector with the i-th component equal to 1, then ( 32) and ( 33) can be written in a vector form as

x(t + 1) = P (t)x(t) (34)
where x(t) = [x 1 (t), . . . , x N (t)] * denotes the state of the overall system. Note that P (t) is a doubly stochastic matrix. It is well known [START_REF] Fagnani | Randomized consensus algorithms over large scale networks[END_REF][START_REF] Jadbabaie | A necessary and sufficient condition for consensus over random networks[END_REF] that, if the graph G is connected and each edge (i, j) ∈ E can be selected with a strictly positive probability W (i,j) , then (34) reaches, almost surely, the average consensus, namely lim t→∞ x(t) = x ave 1, where x ave = 1 N 1 * x(0). In the sequel, we make the following assumption. Assumption 1. The graph G = (V, E) is a undirected connected graph and, at every time instant t ≥ 0, each edge (i, j) ∈ E can be selected with a strictly positive probability W (i,j) .

Note that the algorithm (34) relies upon a crucial assumption: each agent transmits to its neighboring agents the precise value of its state. This implies the exchange of perfect information through the communication network. In this work, we consider a more realistic case, i.e., we assume that the communication network is constituted of rate-constrained digital links. This prevents the agents from having a precise knowledge about the state of the other agents. In fact, through a digital channel, the i-th agent can only send to its neighbors symbolic data in a finite alphabet: using only this data, the neighbors of the i-th agent can build an estimate of the i-th agent's state. We denote this estimate by xi (t), and let x(t) = [x 1 (t), . . . , xN (t)] * . In this work, the estimate is simply the received symbol.

We proceed now by illustrating two types of quantizers which have been introduced in the literature in order to transmit information through a digital channel, for consensus purposes. In [START_REF] Carli | Average consensus on networks with transmission noise or quantization[END_REF][START_REF]Average consensus on networks with quantized communication[END_REF], the authors analyze the case in which

xi (t) = q d (x i (t)), (35)
where, given a real number z, q d : R → Z is the mapping sending z to its nearest integer, namely,

q d (z) = n ∈ Z ⇔ z ∈ [n -1/2, n + 1/2[, if z ≥ 0 z ∈ ]n -1/2, n + 1/2], if z < 0. ( 36
)
We refer to this quantizer as the deterministic quantizer. Instead in [START_REF] Aysal | Distributed average consensus using probabilistic quantization[END_REF][START_REF] Lou | Decentralized estimation in an inhomogeneous sensing environment[END_REF], the socalled probabilistic quantizer is introduced. This quantizer is defined as follows.

Let x ∈ R and let q p (•) denote the probabilistic quantizer. As for the deterministic quantizer above described, the set of quantization levels is the integer numbers, and q p (x) is the binary random variable defined as

q p (x) =
x with probability x -x x with probability x -x , [START_REF] Tatikonda | Control over noisy channels[END_REF] where we let • and • denote the floor and ceiling operators from R to Z. The following straightforward lemma states two important properties of the probabilistic quantizer.

Lemma 7. Let q p (x) be a probabilistic quantization of x ∈ R. Then q p (x) is an unbiased representation of x, i.e.,

E [q p (x)] = x. ( 38
)
Moreover

E (x -q p (x)) 2 ≤ 1 4 . ( 39
)
From now on, with a slight abuse of notation, given a vector x ∈ R N , we use the notation q d (x) ∈ R N (respectively q p (x) ∈ R N ) to denote the vector such that q d (x) = [q d (x 1 ), . . . , q d (x N )] * (respectively q p (x) = [q p (x 1 ), . . . , q p (x N )] * ).

In that paper, we introduce two updating rules of the state using quantized information. In the first strategy, if (i, j) is the edge selected at the t-th iteration, i and j, in order to update its state, use only the estimates of their states, as follows,

x i (t + 1) = 1 2 xi (t) + 1 2 xj (t) x j (t + 1) = 1 2 xj (t) + 1 2 xi (t), (40)
or, equivalently in vector form, by recalling the definition of P (t),

x(t + 1) = P (t)x(t). ( 41
)
To define the second strategy, we remark that (32) can be written as

x i (t + 1) = x i (t) - 1 2 x i (t) + 1 2
x j (t)

x j (t + 1) = x j (t) - 1 2 x j (t) + 1 2 x i (t).
We then propose the following updating rule, where the agents use also perfect information regarding their own states,

x i (t + 1) = x i (t) - 1 2 xi (t) + 1 2 xj (t) x j (t + 1) = x j (t) - 1 2 xj (t) + 1 2 xi (t), (42)
or, equivalently in vector form,

x(t + 1) = x(t) + (P (t) -I)x(t). ( 43
)
We call the law (40) globally quantized and the law (42) partially quantized. It is easy to see that the partially quantized law (42), as the law (32), maintains the initial state average. Formally, defining x ave (t) = 1 N 1 * x(t), we have that the globally quantized law (40) satisfies x ave (t) = x ave (0), for all t ≥ 0. Indeed, it is immediate to verify that 1 * x(t + 1) = 1 * x(t) + 1 * (P (t) -I)x(t) = 1 * x(t), where the last equality follows from the fact that, since P (t) is doubly stochastic for all t ≥ 0, then 1 * (P (t) -I) = 0 for all t ≥ 0. We proceed with our analysis of these two rules by assuming first that xi (t) = q d (x i (t)), i.e., the information transmitted is quantized by means of deterministic quantizer, and then by assuming that xi (t) = q p (x i (t)), i.e., the information transmitted is quantized by means of probabilistic quantizer.

Remark 2. It is clear that with no loss of generality we can assume that the quantization step is equal to 1. More general quantizers, with quantization step a generic positive real number , can be obtained from q d and q p by defining q ( ) d (x) = q d (x/ ) and q ( ) p (x) = q p (x/ ). Hence, the general case can be simply recovered by a suitable scaling.

Quantized gossip algorithms via static deterministic quantizers

In this section we assume that the information exchanged between the agents is quantized by means of the deterministic quantizer q d described in [START_REF] Jadbabaie | A necessary and sufficient condition for consensus over random networks[END_REF], namely xi (t) = q d (x i (t)). In this context, we separately analyze the partially and globally quantized strategies, starting from the first one.

Partially quantized strategy Consider the partially quantized strategy

x i (t + 1) = x i (t) - 1 2 q d (x i (t)) + 1 2 q d (x j (t)) x j (t + 1) = x j (t) - 1 2 q d (x j (t)) + 1 2 q d (x i (t)). (44)
Define

y(t) = I - 1 N 11 * x(t) = x(t) - 1 N 11 * x(0) , (45)
and

d(t) = 1 √ N y(t) 2 . ( 46
)
Such quantity represents the distance of the state x(t) from the average of the states.

As an example we report in Fig. 4 the result of simulations relative to a connected random geometric graph. Such graph has been drawn placing N = 50 nodes uniformly at random inside the unit square and connecting two nodes whenever the distance between them is less that R = 0.3. The initial condition x i (0) is randomly chosen inside the interval [-100, 100] for all 1 ≤ i ≤ N . Note that d(t) does not converge to 0, meaning that the average consensus is not reached. However its value gets very close to 0, implying that the values of the state get very close to the initial average.

In the following we will give a general formal proof of this fact, quantifying the distance from consensus the states of the agents asymptotically achieve. Theorem 2. Consider the algorithm (44). Then, almost surely, there exists

T con ∈ N such that |x i (t) -x j (t)| ≤ 1 ∀ i, j ∀ t ≥ T con , ( 47
)
and hence,

x(t) -x ave 1 ∞ ≤ 1.
Remark 3. Another feature of the algorithms proposed in [START_REF] Kashyap | Quantized consensus[END_REF] is that the state of each node is always an integer. On one hand this represents a clear advantage from a computational point of view. On the other hand, the nodes, at the initial step, have to quantize the initial conditions that could be any arbitrary real number. In general the average of the quantized states will be different from the average of the initial states, thus introducing an error that will be propagated along the iterations of the algorithm. This fact is illustrated in Fig. 5 where we provide a comparison between the partially quantized strategy via deterministic quantizers and the algorithm proposed in [START_REF] Kashyap | Quantized consensus[END_REF], that we denote by KBS. Precisely, we plotted the behavior of d(t) for both strategies on the same graph considered in Fig. 4. 46), for the partially quantized strategy with deterministic quantization, and for the algorithm KBS Globally quantized strategy In this paragraph we consider the globally quantized strategy

x i (t + 1) = 1 2 q d (x i (t)) + 1 2 q d (x j (t)) x j (t + 1) = 1 2 q d (x j (t)) + 1 2 q d (x i (t)). (48)
We underline immediately that the fact that (48) uses only quantized information and not perfect information combined with quantized information as in (44) makes the analysis of (44) slightly easier than the analysis of (48). Remarkably, we show in this subsection that the law (44) drives, almost surely, the systems to exact consensus at an integer value. Unfortunately, the initial average of states is not preserved in general. In this case the following result can be obtained.

Theorem 3. Let x(t) evolve according to (48). Then almost surely there exists T con ∈ N and α ∈ Z such that x i (t) = α for all i ∈ V and for all t ≥ T con .

We have already underlined the fact that this strategy does not preserve the initial average, in general. Providing some probabilistic estimation of the distance of the consensus point from the initial average is a challenging problem: we limits our analysis to the following simulation. In Fig. 6 we plot the variable z that is defined as follows. In the globally quantized strategy we have that, almost surely lim t→∞ = α1 for some random integer α. Let z = |α -1/N 1 * x(0)|. In words, z represents the distance from the consensus point to which the globally quantized strategy leads the systems and the average of the initial condition. We have depicted the value of z for a family of random geometric graphs [START_REF] Penrose | Random Geometric Graphs[END_REF] of increasing size from N = 10 up to N = 80. The initial condition x i (0) is chosen randomly inside the interval [-100, 100] for all 1 ≤ i ≤ N. Moreover for each N , z is computed as the mean of 100 trials. We can see that the value of z is increasing in N and assumes values that are not negligible with respect to the quantization step size.

Speed of convergence Providing insights on the speed of convergence of (44) and of (48) is quite hard in general. In Fig. 7 and Fig. 8 we report, respectively, a comparison between the partially quantized strategy (44) and the gossip algorithm with exchange of perfect information [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF] and between the globally quantized strategy (48) and again the gossip algorithm with exchange of perfect information [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF]. The simulations are made on the same random geometric graphs considered in Fig. 4, and the initial conditions are randomly chosen inside the interval [-100, 100].

For both strategies we plotted the behavior of the variable d(t) defined in (46).

From Fig. 7 and Fig. 8 we can infer that the speed of convergence toward the steady state of the quantized strategies (48) and ( 44) is similar to the one of the gossip algorithm with perfect exchange of information. This numerical evidence is not completely understood yet, but some interesting preliminary results appear in [START_REF] Frasca | Average consensus by gossip algorithms with quantized communication[END_REF]. Remark 4. If, depending on the application, one can not relax the convergence requirement, we could suggest the following heuristic solution to the consensus problem, which combines the positive features of both strategies,

x(t + 1) = P q d (x(t)) + (t)(x(t) -q d (x(t))),
where (t), t ≥ 0, is a nonnegative sequence such that (t) ≤ 1, ∀ t ≥ 0 and lim t→∞ (t) = 0.

Quantized gossip algorithms via static probabilistic quantizers

In this section we assume that the information exchanged between the systems is quantized by means of the probabilistic quantizer q p described in [START_REF] Tatikonda | Control over noisy channels[END_REF], namely xi (t) = q p (x i (t)). We recall the statistics of q p , as illustrated in Lemma 7. Moreover, we make the following natural assumption Assumption 2. Given the values x i (t) for all i ∈ V , the random variables q p (x i (t)), as i varies, form an independent set. Moreover, for every i = j, given x i (t), q p (x i (t)) is independent from x j (t).

As before, we will now separately analyze the partially and globally quantized strategies.

Partially quantized strategy The algorithm for partially quantized strategy, when the edge (i, j) is chosen, can be written as

x i (t + 1) = x i (t) - 1 2
q p (x i (t)) + 1 2 q p (x j (t))

x j (t + 1) = x j (t) -

1 2 q p (x j (t)) + 1 2 q p (x i (t)). (49)
Similarly to the partially quantized strategy via deterministic quantizers (44), also (49) does not reach the consensus in general. Again we report a simulation showing this fact. In Fig. 9 the behavior of the quantity d(t), defined in (46), is depicted for the same connected random geometric graph considered in Fig. 4. Note that the quantity d(t) stays visibly away from 0, meaning that the average consensus is not reached.

The analysis of (49) is more complicate than for the corresponding law (44). This is mainly due to the lack of convexity properties which were used in the analysis of (44). The following example shows this type of difficulty.

Example 1. Consider (44) and assume that the edge (i, j) has been selected at time t. Without loss of generality assume that x i (t) ≤ x j (t). Then, by convexity arguments, we have that x i (t) ≤ x i (t+1), x j (t+1) ≤ x j (t) . This is no longer true for (49). As a numerical example assume that x i (t) = 3.4 and x j (t) = 3.6. Then with probability 1/4 we will have that q p (x i (t)) = 4 and q p (x j (t)) = 3. In this case, by (49), we have that x i (t + 1) = 2.9 and that x j (t + 1) = 4.1. Hence, x i (t + 1), x j (t + 1) do not belong to the interval [ x i (t) , x j (t) ].

For this reason, we do not develop a symbolic analysis for this algorithm, and we do not prove convergence in finite time. By simulations we can see that (49) does not drive the states of the systems inside the same bin of quantization, as the corresponding strategy (44) using deterministic quantizers. In Fig. 10, we depict the behavior of the quantity

s(t) = max 1 ≤ i,j ≤ N |x i (t) -x j (t)|.
for the same random geometric graph considered in Fig. 9. In this simulation we assume that the initial condition x i (0) is randomly chosen inside the interval (49), in terms of both the asymptotic distance from the initial average and the speed of convergence, can be provided by a mean-square analysis. In the sequel of this subsection, we assume that the initial condition x(0) satisfies the following condition.

Assumption 3. The initial condition x(0) is a random variable such that E[x(0)] = 0 and E [x(0)x * (0)] = σ 2 0 I for some σ 2 0 > 0.

Theorem 5. Let x(t) evolve following (59). Then almost surely there exists T con ∈ N and α ∈ Z such that x i (t) = α for all i ∈ V and for all t ≥ T con .

As for (48), it is an open problem to provide a theoretical estimation of the distance between the consensus point to which (59) leads the systems, and the average of the initial condition. We limit our analysis to the following simulations. In Fig. 11 we plot the variable z as previously defined for the globally quantized strategy using deterministic quantizers, i.e., z = |c -1/N 1 * x(0)| where c is such that lim t→∞ x(t) = c1. The variable z represents the distance between the consensus point to which the globally quantized strategy leads the systems and the average of the initial condition. We plot the value of z for a family of random geometric graphs of increasing size from N = 10 up to N = 80. The initial condition x i (0) is chosen randomly inside the interval [-100, 100] for all 1 ≤ i ≤ N. Moreover for each N , z is calculated as the mean of 100 trials. In Fig. 12 provide a comparison between (48) and (59). Surprisingly, the globally quantized strategy using probabilistic quantizers, differently from the globally quantized strategy using deterministic quantizers, seems to reach the consensus very close to the average of the initial condition.

Remark 5. Observe that the strategies we proposed require in principle infinite capacity because the data are quantized through uniform quantizer with infinitely many levels. However, it is easy to see that only finitely many levels of this quantizer are used during the consensus evolution and that the number of this levels depend on the amplitude of the initial states. Therefore only finite capacity communication channels are indeed needed and the capacities depend on the ratio between the initial and the final state dispersion.

Consensus over noiseless digital channels -Dynamic encoding

In this section we will propose the coding techniques for consensus algorithms in the case of noiseless digital channels proposed in [START_REF] Baldan | An efficient quantization algorithm for solving average-consensus problems[END_REF]. This methodology has already been described in details in the Deliverable D02.03 -Communication Network Design rel. 1 where its advantages in solving the consensus problem have been emphasized. Here we recall briefly the algorithm and focus on the advantages and disadvantages of this procedure with respect to the static encoding proposed above.

Here we start from a version of the standard consensus algorithm [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF] whose evolution is given by

x i (t + 1) = N i=1 p ij x j (t), (60)
where p ij are coefficients complying with the communication constraints between agents, thus p ij = 0 only if the edge (i, j) belongs to E. Equation 60 imply that every agent, during algorithm evolution, keeps update his state with a proper average among his state and those of his neighbours. More compactly we can write x(t + 1) = P x(t) = (I + K)x(t),

where P = (p ij ) ∈ R N ×N , K = (k ij ) = P -I and x(t) ∈ R N groups all agents states in a single state vector.

In [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF] it is shown that, if the graph G is strongly connected, every irreducible doubly stochastic1 matrix P drives the system dynamic to the consensus, namely

lim t→∞ x(t) = 1 T x(0) N 1, (62)
where 1 ∈ R N is the vector of all ones. This simply algorithm implicitly assumes also that the communication network is ideal, so that real numbers are exchanged between agents without any loss or degradation of information. Of course this assumption, in real applications, is not realistic due to energy and bandwidth limitations. We assume here that the data exchange between the agents can occur only through a digital noiseless channel. We propose here the Zoom in/Zoom out (ZIZO) algorithm overcome this constraint. The idea behind ZIZO-algorithm is to slightly modify equation 60 in order to obtain a state evolution of the form

x i (t + 1) = x i (t) + N j=1 K ij xij (t), (63)
where xij (t) ∀j : (i, j) ∈ E, the estimations, made by the agent i, of his neighbour j state as well as the estimation of his own measure even if this could seems paradoxical. Now we propose a method for obtaining xij (t). The general structure of the coding scheme is shown in the following picture.

Σ Σ

f f -1 x j (t) xij (t) Channel ξ e j (t) ξ d ij (t) ξ e j (0) ξ d ij (0) l j (t) l j (t) ! " # $ % & ' ( & # $ % & '
where f : R 3 → R. More precisely f (x; ξ) is a static function which is a quantizer with respect to the first variable x and in which the variable ξ is a parameter fixing the characteristic of the quantizer. The function f -1 (l; ξ) is instead a right inverse of f (x; ξ), namely any function such that

f (f -1 (l; ξ); ξ) = l
The block Σ instead is a nonlinear state system with input l(t) and state ξ(t), coinciding with the output, and this system is described by the following equations

ξ(t + 1) = F (ξ(t), l(t))
The remarkable property of this scheme is that, if the states of two systems Σ 's are initialized at the same values, and if the channel is noiseless so that the two systems are fed with the same input evolution, then the states of these two systems will continue to be the same, namely if ξ e j (0) = ξ d ij (0), then ξ e j (t) = ξ d ij (t) for all t. Under this hypothesis we have that the relation between the input x i (t) and the output xij (t) becomes the following: ξ e j (t + 1) = F (ξ e j (t), l j (t)) l j (t) = f (x j (t); ξ e j (t)) xij (t) = f -1 (l j (t); ξ e j (t))

Notice n this way that in fact xij (t) depends only on the index j.

In the ZIZO algorithm we proposed the state ξ e j (t) has two real components xe j (t), z e j (t). The quantizer f is defined as

f (x; x, z) := q d x - x q|z|
where q d (x) is the normalized uniform quantizer defined in [START_REF] Jadbabaie | A necessary and sufficient condition for consensus over random networks[END_REF] and where q is a design parameter. The number x allows to translate the uniform quantizer while the number z allows to zoom the uniform quantizer.

where k 1 , k 2 are design parameters.

The algorithm has three positive parameters k 1 , k 2 and q as well as the matrix of coefficients K which is supposed to be given and designed to obtain, in the linear case, a suitable convergence rate over a given graph.

It is clear that the magnitude of zoom factors afflict the state estimations accuracy. The bigger the zoom factors are, the roughly the estimations will be; this zoom-reliant estimation behaviour justify the name given to the algorithm. Since zoom factors z e j (t) play such a fundamental role, particular care was given to the design of their dynamics. More precisely in the third of 65, the term k 2 l j (t)q|z e j (t)| should guarantee the zoom factors to follow the difference between real states and estimations, thus improving the estimation quality as well as the estimations come close to the real states. The term k 1 |z e j (t)|sgn{l j (t)q|z e j (t)|}, on the other hand, prevent zoom factors from becoming too small in a single algorithm step as a consequence of a fortuitous coincidence between states and estimations

The main result of [START_REF] Baldan | An efficient quantization algorithm for solving average-consensus problems[END_REF] is that, with a suitable choice of the parameters q, k 1 , k 2 the previous adaptation of the consensus algorithm to the case of quantized information exchange between agents yields exact average consensus. Remark 6. The big disadvantage of the proposed solution is that in principle it requires infinite capacity because the data are quantized through uniform quantizer with infinitely many levels. Moreover, differently form what happened for the previous solution, it is not possible to prove that only finitely many levels of this quantizer are used during the consensus evolution. However we have noticed through numerous simulations that using a saturate version of the quantizer, namely a quantizer such that |q(x)| = M for all x such that |x| > M , the evolution of the consensus algorithm with the ZIZO-algorithm does not change much with respect to the case with infinite levels. The proof of convergence of the consensus algorithm with the ZIZO-algorithm and with saturated quantizer is the subject of our present work.

Moreover the proposed strategy strongly resorts to the hypothesis that the channel is noiseless. Indeed, simulations suggest that it does not work well in case of noisy digital channel such are binary symmetric channels or erasure channels.

Conclusion

In this document we reported the advances obtained within the project on the field of control and estimation under communication constrained resources.

In section 2 we introduced a new adaptive differential coding algorithm for systems controlled over digital noiseless channels subject to limited bit rate con-straint. As shown, the proposed algorithm provides robustness against disturbances; while improving transient behavior. Furthermore, the global stability is reached; while the rate theoretical limits are achieved under constant length coding. These are obtained by introducing a Dwell -Time state in addition of ZI and ZO classical modes.

In section 3 we analyzed the consensus algorithm, which can be used for distributed estimation, when the data exchange occurs through a digital noisy channel. We considered both the case in which the encoders are static and the case in which the encoders are dynamic (adaptive). In the case of the static encoding we studied the gossip algorithm for the consensus problem with quantized communication. In order to face the effects due to the quantization (both deterministic and probabilistic) we proposed two updating rules: the globally quantized strategy and the partially quantized strategy. In the former the nodes use only quantized information in order to update their state. In the latter they have access also to exact information regarding their own state. We summarize our results in the following table.

Globally Quant.

Partially Quant. We have provided some simulations characterizing the distance between the consensus point and the initial average. While using the deterministic quantizer this distance turns out to be not negligible, with the probabilistic quantizer the consensus is reached surprisingly very close to the average of the initial condition. Providing some theoretical insights on this fact will be the object of future research. A second issue which deserves attention is the speed of convergence of the presented algorithms. Indeed, the non-quantized gossip algorithm [START_REF] Boyd | Randomized gossip algorithms[END_REF] is known to asymptotically converge, in a mean squared sense, at exponential speed, with a rate which depends on the matrix W. It is thus natural to conjecture that the convergence of the quantized version will be roughly exponential, as long as the differences states are much larger than the quantization step. Preliminary results in this sense are in [START_REF] Frasca | Average consensus by gossip algorithms with quantized communication[END_REF] and in Section 3.3. However, the granularity effects eventually comes out in the convergence, making the systems converge in finite time to some limit point: estimates on such a time are sought in [START_REF] Kashyap | Quantized consensus[END_REF] and in the pair of recent papers [START_REF] Murray | On quantized consensus by means of gossip algorithm -Part I: Convergence proof[END_REF][START_REF]On quantized consensus by means of gossip algorithm -Part II: Convergence time[END_REF]. Giving a rigorous and complete clarification of this question is an interesting open problem.

We showed moreover that a dynamic encoding allows to obtain much higher performance. As mentioned in section 3 many important questions remain open in this set up. One of the most important is providing a mathematical proof of the convergence of those algorithms in the case of limited capacity channels, since the proof we have holds only for infinite levels uniform quantizers. The extension to uniform quantizers with finitely many levels is one the subjects of our present research activity.

Figure 1 :

 1 Figure 1: Closed-loop system with Dwell-Time delta modulation.

Figure 2 :

 2 Figure 2: Example of quantization of one state variable with 3 words per signal.

Figure 3 :

 3 Figure 3: D-ZIZO state machine for multivariable systems and M i ≥ 3.

Lemma 5 (

 5 Transition from Zoom-In to Dwell-Time). Suppose that the algorithm switches to Dwell-Time mode at time k, and y(k) ∈ B ext . Then, in this mode at time k + 1, we also have y(k + 1) ∈ B ext . The algorithm behavior in Dwell-Time mode can be analyzed along the same lines of Lemma 4 with C in replaced by 1, and y(k) ∈ B ext .

  x(k + 1) = (A -BK)x(k) + BKT (k)z(k) Since A -BK is Schur, then if we prove that z(k) converges to 0, we obtain global stability. The adaptive quantization law, D-ZIZO, provides this property. Lemma 3 proves that there exists a finite time k catch such that y(k) ∈ B ext , ∀k ≥ k catch and ∆(k catch ) is finite. Lemma 4 and Lemma 5 imply respectively that in Zoom -In mode and Dwell -Time mode, B ext is invariant. With Lemma 6, at the end of Dwell -Time mode, the condition C T is never activated (in normal conditions) due to the invariance property of B ext . Therefore, the adaptive quantization law always switches between Dwell -Time mode and Zoom -In mode. If we decompose this switching, each cycle is composed of ν samples in Dwell -Time mode with ∆(k + 1) = ∆(k) and at least one sample in Zoom -In mode with ∆(k + 1) = C in ∆(k). Hence, we obtain the following inequality for all k > k catch :

Figure 4 :

 4 Figure 4: Behavior of d for a connected random graph with N = 50 in case of deterministic quantizers and of partially quantized strategy.

Figure 5 :

 5 Figure 5: Plot of d(t), as in (46), for the partially quantized strategy with deterministic quantization, and for the algorithm KBS

Figure 6 :

 6 Figure 6: Behavior of z for a family of random geometric graphs in case of deterministic quantizers and of globally quantized strategy.

Figure 7 :

 7 Figure7: Behavior of d, when using the partially quantized strategy, for a connected random geometric graph with N = 50. Note that since the partially quantized strategy does not converge to a consensus, d(t) does not go to 0.

Figure 8 :

 8 Figure 8: Behavior of d, when using the globally quantized strategy, for a connected random geometric graph with N = 50. In this case, accordingly to the theoretical result stated in Theorem 3, d(t) tends to 0.

Figure 9 :

 9 Figure 9: Behavior of d for a connected random geometric graph with N = 50.

Figure 10 :

 10 Figure 10: Behavior of s for a connected random geometric graph with N = 50.

  we

Figure 11 :

 11 Figure 11: Behavior of z for a family of random geometric graphs when considering the globally quantized strategy using probabilistic quantizers.

Figure 12 :

 12 Figure12: Comparison in terms of z between the "deterministic" and the "probabilistic" strategy, for a family of random geometric graphs.

Deterministic

  Finite time conv. to consensus Larger averaging error Finite time conv. to N -1/2 x -x ave 1 2 ≤ 1/2 Average preserved Probabilistic Finite time conv. to consensus Smaller averaging error Asympt. conv. to N -1/2 E[ x -x ave 1 2 2 ] ≤ 1/2 Average preserved

Under the assumption made on the graph, it is always possible to find such a matrix complying with communication constraints.

We start by observing that (49) can be rewritten as x(t + 1) = P (t)x(t) + (P (t) -I) (q p (x(t)) -x(t))

(50) Define e(t) = q p (x(t)) -x(t),

the quantization error and recall the definition of y(t) given in (45). From (50), using the fact that P (t) is symmetric and stochastic, we easily obtain the following recursive relation in terms of the variables e(t) and y(t)

In order to perform an asymptotic analysis of (51) it is convenient to introduce the following matrices. Let

From the fact that x(0) is a random variable satisfying Assumption 3, it immediately follows that

The following proposition states some correlation properties of the variables y and e.

Proposition 1. Consider the variables y(t) and e(t) above defined. Then

where the right-hand-side is a diagonal matrix whose diagonal elements

for all t ≥ 0.

From the above properties we have that (52) can be rewritten as

To estimate the asymptotic distance from the initial average, we introduce the cost function

The cost depends on the selection probabilities W , and, thanks to the above definitions, can be computed as

We can find the following result.

Theorem 4. For all selection probability matrix W we have that J(W ) ≤ 1 2 . From these theorems we draw a strong conclusion about the convergence of the algorithm. In spite of missing consensus in the strict sense, the asymptotical mean squared error of the algorithm is smaller than the size of the quantization bin, and has a bound which does not depend on the number of the agents, nor on the topology of the graph, nor on the probability of the edges selection.

Globally quantized strategy The algorithm for the globally quantized strategy, when the edge (i, j) is chosen, can be written as

Below we prove that the law (59), as the law (48), drives almost surely the systems to exact consensus at an integer value. Moreover, we show by simulations, that the consensus point, even if (59) does not preserve the average of the state, is rather close to the average of the initial condition. This represents a significant improvement with respect to the strategy (48), that, as seen in Fig. 6, leads to a consensus point whose distance from the average of the initial condition, is not negligible in general.

We can obtain the following convergence result.