Quantized Consensus of Multi-agent Systems with Additive Noise

Abstract

This paper investigates the average consensus problem of multiple discrete-time integrator agents under communication constraints and additive noise. In real applications, both quantization error and additive noise are often unavoidable and may terribly degrade the consensus performance. To handle quantization, we adopt a distributed dynamic encoding and decoding policy, under which the resolution of quantizers can change over time to tightly catch up the states and provide more accurate information. Moreover, bounded additive noise is considered. By generalizing the original noise-free protocol in [14], we propose a modified protocol with a new scaling function and prove that under our protocol, one can achieve approximate consensus even with 1 bit per channel use under the perturbation of additive noise. Furthermore we set up a quantitative relationship between the consensus performance, measured by the ultimate consensus error bound, and the number of available bits per channel use.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In recent years more and more attention has been paid to the distributed coordination of networked multi-agent systems due to its wide application areas, such as coordination control of Unmanned Aerial Vehicle (UAV) [2], flocking [3], rendezvous [4] and formation control [5]. (More details can be found in [1]). When it comes to the consensus problem, each agent has to implement a distributed protocol based on the limited information about itself and its neighboring agents.

Traditional consensus problems have been well solved [6, 7] when all agents can continuously exchange state information with infinite information precision. However, constraints on sensor cost, communication bandwidth, and energy budget dictate that information transmitted between agents has to be quantized, which yields unavoidable quantization error. For the single-agent systems, the bit rate conditions to stabilize systems are derived in [8–10]. Some results of the single-agent systems are adopted to multi-agent systems, [11–13] where the quantized variables are allowed to be any integer, i.e., their quantization ranges are the whole integer set and an infinite bandwidth is needed to transmit such quantized variables, which is difficult to implement in reality.

To overcome the above unrealistic infinite bandwidth requirement, the Minimum Data Rate(MDR) problem is investigated in the field of quantized consensus of multi-agent system. [14] proposes a distributed protocol based on dynamic encoding and decoding and prove that under its protocol, average consensus can be achieved for a connected network with merely one bit information exchange between adjacent agents. More general systems were considered in [15, 16]. But all these results do not consider process noise. If we simply implement them, the desired consensus could be broken due to the additive process noise.

In this paper, we generalize the existing results to handle additive process noise. We first design a new scaling function, which takes the effects of the additive noise into account. Then we propose a modified consensus protocol based on the new scaling function and show that a uniform quantizer utilizing this protocol will never be saturated and the system will achieve approximate consensus with bounded consensus error. Furthermore, we provide a quantitative relationship between the number of available bits per channel use and the consensus performance, measured by the ultimate consensus error.

The rest of this paper is organized as follows. Section 2 presents the models of the communication network and agents, and the basic consensus protocol. In Sect. 3, we propose the modified consensus protocol and prove that approximate average consensus can be achieved under our protocol. Section 4 examines the achieved theoretical results through extensive simulations. Some concluding remarks and future research topics are presented in Sect. 5. To improve readability, technical proofs are placed in the Appendix.

Notations: I denotes an proper dimensional identity matrix and the subscript is omitted for short. $\mathbf 1=[1,...,1]^T$ is a proper dimensional vector with all elements equal to 1 and $J_N=\frac{1}{N} \mathbf 1 \mathbf 1^T$. $\Vert \cdot \Vert$ and $\Vert \cdot \Vert _\infty$ respectively represent the Euclidean and infinity norms on vectors or their induced norms on matrices.

2 Mathematical Models

2.1 Communication Graph

An undirected graph $\mathcal G=\{\mathcal V,\mathcal E,\mathcal A\}$ is used to represent the communication topology of N agents, where $\mathcal V=\{1,2,...,N\}$ is the index set of N agents with i representing the ith agent, $\mathcal E \subseteq \mathcal V \times \mathcal V$ is the edge set of paired agents and $\mathcal A=[a_{ij}] \in \mathbb R^{N \times N}$ with nonnegative elements $a_{ij} \in \{0,1\}$ is the weighted adjacency matrix of $\mathcal G$. Note that $\mathcal {A}$ is a symmetric matrix. An edge $(j,i)\in \mathcal E$ if and only if $a_{ij}=1$, which means that agent j can send information to agent i. The neighborhood of the ith agent is denoted by $N_i=\{j \in \mathcal V|(i,j) \in \mathcal E\}$. $D_i=|N_i|$ is called the degree of agent i and $D^\star =\max _i D_i$ is called the degree of $\mathcal G$. A sequence of edges $(i_1,i_2),(i_2,i_3),...,(i_{k-1},i_k)$ is called a path from agent $i_1$ to agent $i_k$. The graph $\mathcal G$ is called a connected graph if for any $i,j \in \mathcal V$, there exists at least one path from i to j. Denote $\mathcal D = diag(D_1,...,D_N)$ and the Laplacian matrix of $\mathcal G$ by $\mathcal L= \mathcal D- \mathcal A$. The eigenvalues of $\mathcal L$ in an ascending order are denoted by $0=\lambda _1\le \lambda _2 \le ... \le \lambda _N$, where $\lambda _N$ is the spectral radius of $\mathcal L$ and $\lambda _2$ is called the algebraic connectivity of $\mathcal G$.

2.2 Dynamic Encoding and Decoding Algorithms

In a digital communication network, the jth agent possesses an encoder and $D_j$ decoders, each of which serves a neighbor of agent j. The encoder quantizes the state of agent j and encodes it into a bit sequence. The decoders receives the encoded state information of $D_j$ neighbors of agent j and decodes them to generate estimates of the states of neighboring agents.

Encoders implement a $(2L)-$level uniform quantizer $q(\cdot ):\mathbb R \rightarrow \varGamma$, which is a map from $\mathbb R$ to the set of quantized levels $\varGamma =\{\pm i,i=1,2,...,L\}$ and mathematically expressed as

$$\begin{aligned} q(y) = \left\{ \begin{array}{ll} i-1/2,&{}i-1 \le y< i, ~~~i=1,...,L\\ L-1/2,&{}y \ge L\\ -q(-y), &{} y <0 \end{array} \right. \end{aligned}$$

(1)

As [14], we adopt a difference encoder with scaling. More specifically, the encoder $\varPhi _i$ of the ith agent is composed of an estimator and a quantizer, which are given below.

Estimator:

$$\begin{aligned} \left\{ \begin{array}{ll} \xi _{ii}(0)=0,\\ \xi _{ii}(k)=g(k-1)m_i(k)+\xi _{ii}(k-1),~~k=1,2,... \end{array} \right. \end{aligned}$$

(2)

Quantizer:

$$\begin{aligned} m_i(k)=q\left[ \frac{x_i(k)-\xi _{ii}(k-1)}{g(k-1)}\right] ,~~k=1,2,... \end{aligned}$$

(3)

where k is the time step, $x_i$ is the state of the ith agent, $\xi _{ii}(k)$ is the internal state of $\varPhi _i$, and $m_i(k)$ is the information sent to the neighbors of the ith agent. g(k) is the scaling function to be designed. The decoder of the ith agent’s neighbours can decode the information received from agent i and get an estimate of $x_i(k)$, $\xi _{ji}(k)$, according to

$$\begin{aligned} \left\{ \begin{array}{ll} \xi _{ji}(0)=0,\\ \xi _{ji}(k)=g(k-1)m_i(k)+\xi _{ji}(k-1),~~~~k=1,2,... \end{array} \right. \end{aligned}$$

(4)

2.3 System Model

In this paper, the agents are governed by the following integrator dynamics

$$\begin{aligned} x_i(k+1)=x_i(k)+u_i(k)+\omega _i(k)~~~~i=1,...,N~~~~k=0,1,... \end{aligned}$$

(5)

where $x_i(k) \in \mathbb R$ represents the state of the ith agent, $u_i(k)\in \mathbb R$ is the input of the ith agent, $\omega _i(k)\in \mathbb R$ is the additive process noise. In this paper, we assume that the exact states of the neighbours are not available because of quantization. According to (2) and (4), we see that both the ith agent’s encoder and its neighbours’ decoders can get estimates of state $x_i$, and their estimates are exactly the same when there is no delay in the communication channel. Therefore we denote such estimate of $x_i$ as $\hat{x}_i(=\xi _{ii}=\xi _{ji})$. Thus we adopt the following quantized protocol,

$$\begin{aligned} u_i(k)=h\sum \limits _{j \in N_i} a_{ij}\left[ \hat{x}_j(k)-\hat{x}_i(k)\right] ,~~~~i=1,2,...,N \end{aligned}$$

(6)

Denote $X(k)=[x_1(k),...,x_N(k)]^T$, $\widehat{X}(k)=[\hat{x}_1(k),...,\hat{x}_N(k)]^T$ and $\omega (k)=[\omega _1(k),...,\omega _N(k)]^T$. Define the quantization error vector

$$\begin{aligned} \eta (k)=X(k)-\widehat{X}(k) \end{aligned}$$

(7)

and the deviation vector

$$\begin{aligned} \delta (k)=X(k)-J_NX(k) \end{aligned}$$

(8)

By the above notation, we can combine the closed-loop system equation and the coding algorithm together into a matrix form,

$$\begin{aligned} {\left\{ \begin{array}{ll} X(k+1)=(I-h\mathcal L)X(k)+h\mathcal L \eta (k)+\omega (k)\\ \widehat{X}(k+1)=g(k) q\left[ \frac{X(k+1)-\widehat{X}(k)}{g(k)}\right] +\widehat{X}(k) \end{array}\right. }\!\!\!\!\!\!\!, \end{aligned}$$

(9)

where $q(\cdot )$ is the component-wise quantizer, i.e., $q([y_1,...,y_N])=[q(y_1),...,q(y_N)]$ and $\mathcal L$ is the Laplacian matrix of the network.

The following assumptions will be adopted in the subsequent analysis:

• (A1) $||\delta (0)||_\infty \le ||x(0)||_\infty \le B_x$

• (A2) $||\omega (k)||_\infty \le M$, $k=1,2,...$

where $B_x$ and M are some nonnegative constants.

Due to the inclusion of additive process noise, we cannot guarantee the traditional average consensus, i.e., $\lim _{k \rightarrow \infty } \delta (k) =0$. Instead, we pursue the following approximate consensus,

$$\begin{aligned} \lim _{K \rightarrow \infty } \sup _{k \ge K} \Vert \delta (k)\Vert < \infty . \end{aligned}$$

(10)

3 Quantized Consensus Protocol

3.1 Scaling Function Design

The design of the scaling function g(k) is the key point of our quantized consensus protocol, which involves the topology of the communication network and the additive process noise. That design needs the following preliminary result.

Lemma 1

[14] If the topology of network is connected and $h<2/\lambda _N$, then $\rho _h<1$, where

$$\begin{aligned} \rho _h=\max \limits _{2\le i\le N} |1-h\lambda _i|. \end{aligned}$$

(11)

Furthermore, if $h<2/(\lambda _2+\lambda _N)$, then $\rho _h=1-h\lambda _2$.

Remark 1

The maximum eigenvalue of $(I-h\mathcal L)$ is 1 and the others are inside the unit circle. In the following we will show that the convergence rate of the discrete-time system mainly depends on $\rho _h$. To make sure that the quantizer will never saturate and always provide meaningful quantization result, it is necessary to require that the scaling function converge slower than $\rho _h$.

Here we propose a scaling function

$$\begin{aligned} {\left\{ \begin{array}{ll} g(0)=g_0\\ g(k+1)=\gamma g(k)+ M \end{array}\right. } \end{aligned}$$

(12)

where the convergence factor $\gamma \in [ \rho _h,1)$ with $h \in (0,2/\lambda _N)$. Note that M is the norm bound of the additive noise. On the one hand, g(k) still decreases as [14], especially under large $g_0$. On the other hand, there exists an additive “overmeasure” each step so that the additive noise will not result into the saturation of the quantizers. To make sure the scaling function g(k) is monotonically decreasing with respect to k, we choose $g_0>\frac{M}{1-\gamma }$, which will simplify our analysis without loss of generality.

3.2 Quantized Consensus Protocol

Before presenting the quantized consensus protocol, we first analyze the dynamic models of the quantization error and the deviation error. Note that $\mathcal {L} J_N=J_N \mathcal {L} =0$, therefore $h\mathcal {L}\delta (k)=h\mathcal {L}[X(k)-J_NX(k)]=h\mathcal {L}X(k)$.

By the system model (9), we define an innovation vector as

$$\begin{aligned} e(k)=X(k+1)-\widehat{X}(k)=(I+h\mathcal L) \eta (k)-h\mathcal L\delta (k)+\omega (k). \end{aligned}$$

(13)

We can derive

$$\begin{aligned} {\left\{ \begin{array}{ll} \delta (k+1)=(I-h\mathcal L)\delta (k)+h\mathcal L\eta (k)+(I-J_N)\omega (k)\\ \eta (k+1)=e(k)-g(k)q\left( \frac{1}{g(k)}e(k)\right) \end{array}\right. } \end{aligned}$$

(14)

Let $\acute{\delta }(k)=\frac{\delta (k)}{g(k)}$, $\acute{\eta }(k)=\frac{\eta (k)}{g(k)}$ and $\acute{\omega }(k)=\frac{\omega (k)}{g(k)}$. By (12), (14), we get

$$\begin{aligned} {\left\{ \begin{array}{ll} \acute{\delta }(k+1)=G(k)(I-h\mathcal L)\acute{\delta }(k)+G(k)h\mathcal L\acute{\eta }(k)+G(k)(I-J_N)\acute{\omega }(k)\\ \acute{\eta }(k+1)=G(k)\left[ \acute{e}(k)-\mathcal Q(\acute{e}(k))\right] \end{array}\right. } \end{aligned}$$

(15)

where $G(k)=g(k)/g(k+1)$ and

$$\begin{aligned} \acute{e}(k)=\frac{e(k)}{g(k)}=(I+h\mathcal L)\acute{\eta }(k)-h\mathcal L\acute{\delta }(k)+\acute{\omega }(k). \end{aligned}$$

(16)

Note that $\acute{e}(k)$ is exactly the information to be quantized. Now we are ready to present our first consensus result in Theorem 1, whose proof is moved into the Appendix to improve readability.

Theorem 1

Suppose Assumptions $(A1)-(A2)$ hold. For any given $h \in (0,2/\lambda _N)$ and $\gamma \in [\rho _h,1)$, let

$$\begin{aligned} L \ge L(h,\gamma ) \end{aligned}$$

(17)

$$\begin{aligned} L=&h \lambda _N \Bigg [\frac{\sqrt{N} (B_x+g_0)}{g_0} + \frac{\sqrt{N} h \lambda _N M}{2(1-\gamma )} + \frac{\sqrt{N} h \lambda _N [(1-\gamma )g_0-M]}{2 M \gamma e} \Bigg ] \nonumber \\&+ \frac{1+2h D^\star + 2\gamma (1-\gamma )}{2\gamma } \end{aligned}$$

(18)

The protocol given in (2)–(4) and (6) is implemented with 2L-level uniform quantizers (1), the scaling function (12) whose initial value satisfies

$$\begin{aligned} g_0>\max \left\{ \frac{M}{1-\gamma },B_x+M \right\} \end{aligned}$$

(19)

Then the closed-loop system (9) achieves approximate consensus with the following bounded consensus error

$$\begin{aligned} \lim \limits _{k \rightarrow \infty }||\delta (k)|| \le \frac{\sqrt{N} M[ h \lambda _N +2(1-\gamma )]}{2(1-\gamma )^2} \end{aligned}$$

(20)

Remark 2

By (18), we see that the L to achieve the desired approximate consensus is determined by h and $\gamma$. When h is small enough and $\gamma$ is close to 1, L can be as low as 1, i.e., 1 bit per channel use is enough to guarantee that the ultimate consensus error is bounded. Of course, $L=1$ may yield very large consensus error bound in (20). The balance between the required L and the achievable consensus error is critical and will be discussed further in Sect. 3.3.

Remark 3

According to (20), the topology of the communication network, particularly $\lambda _N$, is an important factor of the consensus error. If we choose $h<2/(\lambda _2+\lambda _N)$ and $\gamma =\rho _h$, then $1-\gamma =h\lambda _2$ and

$$\begin{aligned} \lim \limits _{k \rightarrow \infty }||\delta (k)|| \le \frac{\sqrt{N} M}{2h\lambda _2}\left[ \frac{\lambda _N}{\lambda _2}+2\right] \end{aligned}$$

(21)

$\lambda _2$ is defined as the algebraic connectivity of graph in [6] and $\lambda _2/\lambda _N$ is referred to as the eigenratio of an undirected graph [17], which has an upper bound

$$\begin{aligned} \frac{\lambda _2}{\lambda _N} \le \frac{\min _i D_i}{\max _i D_i} \end{aligned}$$

(22)

where $\min _i D_i$ and $\max _i D_i$ represent the minimum and maximum degrees of agents in the communication network, respectively.

When all degrees of agents in the network are relatively large and the difference between the maximum and minimum degrees is relatively small, the system can achieve relatively small consensus error, i.e., more balanced and connected networks yield more accurate consensus.

3.3 Consensus Protocol Control Gain Design

In this subsection, we propose a design method of the control gain when there exists limitations on the communication resource and the quantized consensus performance.

In Theorem 1 we present a quantized consensus protocol to assure the system to achieve approximate consensus utilizing finite bit communication. One can see from the result (18) that the larger the control gain h we choose, the more quantization levels the protocol need. However in practical scenario the communication resource is always limited, therefore the control gain has an upper bound. We show this result in the following lemma and for computation convenience, we choose the convergence factor of the scaling function $\gamma =\rho _h$.

Lemma 2

Suppose Assumptions $(A1)-(A2)$ hold and set $\gamma =\rho _h$. For any given $L_1 \in \mathbb N^+$, under the quantized consensus protocol in Theorem 1 with the $2L_1-$level uniform quantizers, there always exist a control gain $h \in \left( 0,h(L_1)\right)$ that guarantees the closed-loop system (9) to achieve approximate consensus.

Proof

The proof is omitted due to the space limitation.

From equality (21) we know that to achieve accurate approximate consensus, the control gain h should be sufficiently large. So when we set a consensus performance requirement $\delta _1$ that $\lim \limits _{k \rightarrow \infty } ||\delta (k)|| \le \delta _1$, the choice of h has an lower bound $h(\delta _1)$. But when there exists some limitations on the use of communication resource, from the result in Lemma 2 we know that $h(\delta _1)$ should be smaller than $h(L_1)$. Therefore we have the following lemma.

Lemma 3

Suppose Assumptions $(A1)-(A2)$ hold and set $\gamma =\rho _h$. For any given $\delta _1 \in [\underline{\delta },\infty )$, under the quantized consensus protocol in Theorem 1 with $2L_1-$level uniform quantizers, there always exist a control gain $h \in \left( h(\delta _1),\bar{h}\right) ,$ where $\bar{h}=\min \left\{ h(L_1),\frac{2}{\lambda _N}\right\}$ that guarantees the closed-loop system (9) to achieve approximate consensus with consensus error no more that $\delta _1$, where $\underline{\delta }$ and $h(\delta _1)$ satisfy the following equations

(a) When $h \in (0,\frac{2}{\lambda _2+\lambda _N}),\gamma =\rho _h=1-h\lambda _2$,

$$\begin{aligned} h(\delta _1)=\frac{\sqrt{N} M (\lambda _N+2\lambda _2)}{2 \delta _1 \lambda _2^2},~~~~~\underline{\delta }=\frac{\sqrt{N} M (\lambda _N+2\lambda _2)}{2 \bar{h} \lambda _2^2} \end{aligned}$$

(b) When $h \in (\frac{2}{\lambda _2+\lambda _N},\frac{2}{\lambda _N}),~\gamma =\rho _h=h\lambda _N-1$, $h(\delta _1)$ is the root of equation

$$\begin{aligned} 2 \delta _1 \lambda _N h^2x+( \sqrt{N} M \lambda - 8 \delta _1 \lambda _N )h+ (8 \delta _1- 4\sqrt{N} M) =0,~~\underline{\delta }=\frac{\sqrt{N} M (4 - \bar{h} \lambda _N)}{2 (2-\bar{h} \lambda _N)^2} \end{aligned}$$

Consider an complete network of eight agents, i.e. each agent has the access to all the other agents’ information in the network, as an example. From Fig. 1 one can see that as the restricted quantization level $L_1$ increases from 1 to 50, the lower bound of the consensus performance $\underline{\delta }(L_1)$ decreases. The shaded area presents the feasible choice of control gain.

Fig. 1.

Curves of the restricted quantization level $L_1$ and the lower bound $\underline{\delta }(L_1)$

4 Simulations

The validity of the quantized consensus protocol is demonstrated in this section. Consider a multi-agent system consisting of 8 agents with integrator dynamics (9). The interconnection topology is described by a regular undirected graph of degree 4 where the eigenvalues of the Laplacian matrix $\lambda _2=4,\lambda _N=8$.

Set the initial states equal to $X(0)=[5, 10, 15, 20, 25, 30, 35, 40]^T$ and the noise bound $M=0.5$. Choose the control gain $h=0.0045$ and consequently according to (17)–(19) we have $\gamma =\rho _h=0.982,~g(0)=40.5,~L(h,\gamma )=0.799$ and the bit rate $L=1$. Figure 2 illustrates the trajectories of states, the deviation vector’s Euclidean norm and the norm bound we estimate. One can see that all the agents converge to approximate consensus after several steps and the consensus error remain bounded thereafter which verifies our protocol. In this way we sacrifice the system performance to save the communication resource, which is very important in practical scenario.

Fig. 2.

Trajectories of states and Euclidean norm of deviation vector under Network topology one with one bit communication

5 Conclusion

In this paper we show that under the protocol we designed, a group of dynamic agents can achieve approximate consensus even when there exists additive noise. It is shown that the consensus error depends on the scaling function, the consensus gain and the communication topology. Furthermore we propose a way to design the consensus protocol when there exists constrictions on the communication resource and system performance. However achievement of accurate consensus is still a tough mission. Quantizers designed with various structures can only weaken the impact of the additive noise on current state but can not eliminate their cumulative effect in the future.

For future research, robustness with respect to packet-loss, link failures and time-delay may be considered and the results may be extended to high-ordered system.

6 Appendix: Proofs

6.1 Proof of Theorem 1

The proof is consist of two parts. In part 1, we assume that each communication channel between agents possesses adequate communication resources, and therefore we focus on the interruption that the quantization operation and additive noise bring into the system. In part 2, we work on how many data bit is enough on earth for the system to achieve approximate consensus when applied to the quantized consensus protocol.

Part 1. Since matrix $\mathcal L$ is symmetric, we can diagonalize it with the unitary matrix $T=[(1/\sqrt{N})\mathbf 1 ,\phi _2,...,\phi _N]$ defined by . Therefore we have , where $\phi =[\phi _2,...,\phi _N]$, $\varLambda =diag(1-h\lambda _2,...,1-h\lambda _N)$ and 0 is the zero matrix of proper dimension. Then the recursion of the deviation vector (15) can be transformed into

$$\begin{aligned} \acute{\delta }(k+1)= & {} G(k) (\phi \varLambda \phi ^T +J_N) \acute{\delta }(k)+ G(k)h \mathcal L \acute{\eta }(k)\nonumber +G(n) (I-J_N)\acute{\omega }(k) \nonumber \\= & {} G(k) \phi \varLambda \phi ^T \acute{\delta }(k)+ G(n)h \mathcal L \acute{\eta }(k)+G(k) (I-J_N)\acute{\omega }(k) \end{aligned}$$

(23)

where $J_N \acute{\delta }(k) = J_N (I-J_N)X(k)/g(k)=0$. Let$~G_0^k=\prod _{i=0}^k G(i)=\frac{g(0)}{g(k+1)}$ and it follows that

$$\begin{aligned} \Vert \acute{\delta }(k+1)\Vert\le & {} \Vert G_0^k \phi \varLambda ^{k+1} \phi ^T \acute{\delta }(0)\Vert + \Vert h \sum _{j=0}^{k} G_{k-j}^k ( \phi \varLambda \phi ^T)^j \mathcal L \acute{\eta }(k-j)\Vert \nonumber \\&+\ \Vert \sum _{j=0}^{k} G_{k-j}^k ( \phi \varLambda \phi ^T)^j (I-J_N) \acute{w}(k-j)\Vert \end{aligned}$$

(24)

where $( \phi \varLambda \phi ^T)^0=I$.

We estimate the three terms on the right hand of (24) separately.

Note that $\rho _h \le \gamma$, $||\phi ||=||\phi ^T||=1$ and $||x||_\infty \le ||x|| \le \sqrt{N}||x||_\infty$ for any N dimensional vector x. For the first term,

$$\begin{aligned} \left| \left| G_0^k \phi \varLambda ^{k+1} \phi ^T \acute{\delta }(0)\right| \right| _2 \le G_0^k \left( \rho _h \right) ^{k+1} \frac{\sqrt{N}||\delta (0)||_\infty }{g(0)} \le \frac{\sqrt{N} B_x}{g(k+1)} \gamma ^{k+1} \end{aligned}$$

(25)

Since we assumed that each quantizer possesses adequate quantization levels, at each recursion step the quantizers will not be saturated, i.e. the quantization error are no more than 1/2. Then together with (15) one can see that

$$\begin{aligned} \ ||\acute{\eta }(k)||_\infty \le \frac{1}{2}G(k-1) ,~~k=1,2,... \end{aligned}$$

(26)

Note that $||\mathcal L||=\lambda _N$. For the second term, together with (26), we have

$$\begin{aligned}&\left| \left| ~h \sum _{j=0}^{k} G_{k-j}^k ( \phi \varLambda \phi ^T)^j \mathcal L \acute{\eta }(k-j)~\right| \right| _2 \le \sqrt{N} h \lambda _N \left[ \sum \limits _{j=0}^{k}\frac{g(k-j)}{g(k+1)}\left( \rho _h \right) ^{j}\frac{g(k-j-1)}{2g(k-j)}\right] \nonumber \\&~~~~~~~~~~~\le \frac{ \sqrt{N} h \lambda _N}{2 g(k+1)} \left[ (k+1) g_0\gamma ^{k-1}+ M \sum \limits _{j=0}^{k}\sum \limits _{i=0}^{k-j-2}\gamma ^i \gamma ^j \right] \nonumber \\&~~~~~~~~~~~= \frac{\sqrt{N} h \lambda _N}{2g(k+1)} \left( g_0-\frac{M}{1-\gamma }\right) (k+1) \gamma ^{k-1} + \frac{\sqrt{N} h \lambda _N M}{2g(k+1)}\frac{1-\gamma ^{k+1}}{(1-\gamma )^2} \end{aligned}$$

(27)

Similarly for the last term, with the Assumption (A2) and note that $||I-J_N||=1$, we can get

$$\begin{aligned}&\left| \left| ~\sum _{j=0}^{k} G_{k-j}^k ( \phi \varLambda \phi ^T)^j (I-J_N) \acute{w}(k-j)~ \right| \right| _2 \le \frac{\sqrt{N} M}{g(k+1)}\frac{1-\gamma ^{k+1}}{1-\gamma }\nonumber \end{aligned}$$

As proved above we know that the scaled deviation vector $\acute{\delta }(k)$ can be bounded. Moreover, when step k tends to infinity, together with (25), (27) and (28) we have

$$\begin{aligned} \lim _{k \rightarrow \infty }&||\delta (k+1)|| = \lim _{k \rightarrow \infty }g(k+1)||\acute{\delta }(k+1)|| \nonumber \\&\le \lim _{k \rightarrow \infty } \Bigg [ \sqrt{N} B_x \gamma ^{k+1}+ \frac{\sqrt{N} h \lambda _N}{2} \left( g_0-\frac{M}{1-\gamma }\right) (k+1) \gamma ^{k-1}\nonumber \\&~~~ + \frac{\sqrt{N} h \lambda _N M}{2}\frac{1-\gamma ^{k+1}}{(1-\gamma )^2} + \sqrt{N} M \frac{1-\gamma ^{k+1}}{1-\gamma } \Bigg ] \nonumber \\&\le \frac{\sqrt{N} h \lambda _N M}{2(1-\gamma )^2}+ \frac{\sqrt{N} M}{1-\gamma } \end{aligned}$$

(28)

Therefore the closed-loop system can achieve approximate consensus with bounded consensus error.

Part 2. Under a quantized consensus protocol, it is necessary and important that the quantizers will never saturate. Otherwise, what one agent broadcasts could be the saturated value of the state instead of its real value and that saturated information may mislead its neighbours. We prove here that the uniform quantizers (1) with 2L levels will never be saturated when $L\ge L(h,\gamma )$ with the help of mathematical induction.

Note that $\acute{e}(k),~k=1,2,...$ is the information to be quantized. At the initial time, we know that $\widehat{X}(0)=0$. According to Assumption (A1) and (19) we have

$$\begin{aligned} ||\acute{e}(0)||_\infty = ||(I+h\mathcal L)\acute{\eta }(0)-h\mathcal L\acute{\delta }(0) + \omega (0)||_\infty \le \frac{B_x + M}{g_0}< L(h,\gamma )<L \end{aligned}$$

(29)

Hence, when $k=0$ the quantizers are unsaturated.

For any given nonnegative integer n, suppose that when $k=0,1,...,n$ the quantizer are not saturated, i.e. the quantization error are less than 1 / 2. Then at the $n+1$ step,

$$\begin{aligned} ||\acute{e}(n+1)||_\infty\le & {} ||(I+h \mathcal L)||_\infty ||\acute{\eta }(n+1)||_\infty +h||\mathcal L|| ||\acute{\delta }(n+1)|| + ||\acute{\omega }(n+1)||_\infty \nonumber \\\le & {} \frac{1+2h D^\star }{2}G(n)+h \lambda _N ||\acute{\delta }(n+1)|| +\frac{||\omega (n+1)||_\infty }{g(n+1)}\nonumber \\\le & {} \frac{g(n)(1+2h D^\star )}{2[g(n)\gamma +M]}+ h \lambda _N ||\acute{\delta }(n+1)|| + \frac{M(1-\gamma )}{M} \nonumber \\\le & {} \frac{1+2h D^\star }{2\gamma }+ h \lambda _N ||\acute{\delta }(n+1)|| +(1-\gamma ) \end{aligned}$$

(30)

The norm bound of $\acute{\delta }(n+1)$ can be estimated similarly as in the proof of Theroem 1. From (25)–(28), we have

$$\begin{aligned} ||\acute{\delta }(n+1)||\le & {} \frac{\sqrt{N} B_x \gamma ^{n+1}}{g(n+1)}+ \frac{\sqrt{N} h \lambda _N M}{2g(n+1)}\frac{1-\gamma ^{n+1}}{(1-\gamma )^2}+ \frac{\sqrt{N} M}{g(n+1)} \frac{1-\gamma ^{n+1}}{1-\gamma } \nonumber \\&+ \frac{\sqrt{N} h \lambda _N}{2g(n+1)\gamma ^2} \left( g_0-\frac{M}{1-\gamma }\right) (n+1) \gamma ^{n+1} \end{aligned}$$

(31)

Function $f(x)=x\gamma ^x,~x \in \mathbb R,~ \gamma \in (0,1)$ has an upper bound $f(x)\le \frac{1}{-e \log (\gamma )}$ when $x=\frac{1}{- \log (\gamma )}$, where e is the base of the natural logarithm. And since $\gamma \in (0,1)$ we know that $\log (\gamma )\ge 1/\gamma$, then the term $(n+1) \gamma ^{n+1} \le \frac{\gamma }{e}$.

Note that $g(k)> g(\infty )=\frac{M}{1-\gamma }$, we can get

$$\begin{aligned} ||\acute{\delta }(n+1)|| \le \frac{\sqrt{N} B_x}{g_0} + \frac{\sqrt{N} h \lambda _N (1-\gamma )}{2 M \gamma e} g_0 - \frac{\sqrt{N} h \lambda _N }{2 \gamma e} + \frac{\sqrt{N} h \lambda _N M}{2(1-\gamma )} + \sqrt{N} \end{aligned}$$

(32)

Therefore

$$\begin{aligned} ||\acute{e}(n+1)||_\infty \le&~h \lambda _N \Bigg [\frac{\sqrt{N} (B_x+g_0)}{g_0} + \frac{\sqrt{N} h \lambda _N M}{2(1-\gamma )} + \frac{\sqrt{N} h \lambda _N [(1-\gamma )g_0-M]}{2 M \gamma e} \Bigg ]&\nonumber \\&+ \frac{1+2h D^\star }{2\gamma } +(1-\gamma )&\nonumber \\ =&~ L(h,\gamma ) \le L \end{aligned}$$

(33)

So at time $k=n+1$ the quantizers are still unsaturated. Therefore, by induction, we conclude that if a set of (2L)-level uniform quantizers with $L \ge L(h,\gamma )$ are applied to the system, they will never be saturated.

According to the result in part 6.1, under the quantized consensus protocol the agent system can achieve approximate consensus with bounded consensus error.