Robust Consensus for Multi-Agent Systems Communicating
over Stochastic Uncertain Networks ⋆

arXiv:1703.09877v1 [cs.SY] 29 Mar 2017

Zhongkui Li a, Jie Chen b
a

State Key Laboratory for Turbulence and Complex Systems, Department of Mechanics and Engineering Science, College of
Engineering, Peking University, Beijing 100871, China
b

Department of Electronic Engineering, City University of Hong Kong, Kowloon, Hong Kong

Abstract
In this paper, we study the robust consensus problem for a set of discrete-time linear agents to coordinate over an uncertain
communication network, which is to achieve consensus against the transmission errors and noises resulted from the information
exchange between the agents. We model the network by means of communication links subject to multiplicative stochastic
uncertainties, which are susceptible to describing packet dropout, random delay, and fading phenomena. Different communication topologies, such as undirected graphs and leader-follower graphs, are considered. We derive sufficient conditions for robust
consensus in the mean square sense. This results unveil intrinsic constraints on consensus attainment imposed by the network
synchronizability, the unstable agent dynamics, and the channel uncertainty variances. Consensus protocols are designed based
on the state information transmitted over the uncertain channels, by solving a modified algebraic Riccati equation.
Key words: Cooperative control, consensus, uncertainty, communication channel, robustness.

1

Introduction

Over the last decade, consensus and other cooperative
control problems of multi-agent systems have received
compelling attention from the control community; see
the recent works [1,2,3,4] and the references therein.
Roughly speaking, a consensus problem of multi-agent
systems is composed of three essential components, both
independent and inter-related: the agent dynamics, the
network communicating among the agents, and the consensus protocol required to achieve consensus [4]. The
network topology is without any question the central
mechanism that enables multiple agents to cooperate
via information exchange between the agents and over
the network. In the literature, a directed or undirected
graph, commonly represented by a known, often constant matrix, is adopted to characterize the information flow among the agents in a highly idealized manner.
In practice, however, the information exchanges among
agents must be executed over a communication network
⋆ This work was supported in part by the National Natural Science Foundation of China under grants 61473005,
11332001, 61225013, and in part by the Hong Kong RGC
under the project CityU 111613, CityU 11200415.
Email addresses: zhongkli@pku.edu.cn (Zhongkui Li),
jichen@cityu.edu.hk (Jie Chen).

Preprint submitted to Automatica

consisting of various communication links, which cannot
be immune to transmission errors, channel noises, and
system constraints. A realistic multi-agent model must
therefore account for the network communication errors
and noises, and for it to be viable, the theory of cooperative control of multi-agent systems must address the
robustness against the noises and uncertainties in the
communication channels.
Communication errors may result from a variety of
channel constraints and transmission imperfections,
such as data rate limit, quantization precision, time
delay, packet dropout, and channel capacity, etc. These
issues pose novel challenges to feedback design and
have been a focal subject of the recent research on
networked control systems [5,6,7]. By now it is widely
known that for a system controlled over a communication channel, the channel specification, be it data rate,
capacity, quantization density, and signal-to-noise ratio,
must in one way or another satisfy an intrinsic bound
in order to ensure feedback stabilization [8,9,10]. Unsurprisingly, these advances have made their way into
the study of multi-agent systems. Consensus problems
using quantized information exchanges are considered
in, e.g., [11,12]. Conditions are derived in [13,14] to
achieve mean square consensus in the presence of communication or measurement noises. Efforts are made

30 March 2017

tion channel perturbed by a multiplicative uncertainty.
A sufficient condition is obtained similarly to guarantee
the mean square consensus.

in [15,16] to address the effect of data loss or packet
dropout on consensus. Generally, in the presence of
such communication errors, one finds the design of a robust consensus protocol ever more difficult and indeed
a highly nontrivial task, due to the interplay between
the agent dynamics, the communication graph, and the
communication channels.

Previous works pertinent to this paper include [22,23,13,24,25],
where robust consensus over uncertain communication
channels is studied. It should be noted, nonetheless,
that only single-integrator agents are considered in
these works, while the present paper addresses general high-order linear agent dynamics. This difference
in the agent dynamics is by no means simple. Indeed,
even with single-integrator agents, the robust consensus
conditions (see, e.g., [22]) appear rather complex, lest
the conditions for general linear agents. Equally difficult is the task of designing feedback gain matrices of
the consensus protocols. This latter issue is moot with
the aforementioned case of single-integrator agents,
as therein only scalar feedback gains need to be designed. More generally, due to the need to incorporate
the graph structure, the analysis and design of robust
consensus against the multiplicative stochastic uncertainties presents in general a highly nontrivial task,
whose difficulty goes considerably beyond that found in
networked control problems [5,6,7]. Finally, it is worth
pointing out that robustness issues will also arise from
the uncertainties in agent dynamics. This, however, is
not the concern of the current paper; there is a bulk of
research devoted to the study of heterogeneous agents,
see, e.g., [26] and references therein.

In this paper we study the robust consensus problem for
general discrete-time multi-agent systems with stochastic uncertain communication channels. Motivated by the
random quantizers in [17] and the fading channel model
in [18], we model each communication link between the
agents as a noisy communication channel subject to a
multiplicative stochastic uncertainty. A graph network
so formulated provides a more realistic model of the
communication network consisting of erasure channels,
which are particularly susceptible to describing such network losses as packet dropout and random delay. Indeed,
the uncertain channel model herein includes the random quantizers (as pointed out in [17]), the stochastic
i.i.d. packet loss (as demonstrated in [18]), and random
relative-state-dependent measurement noises (as shown
in [13]) as special cases. Our task is twofold. First, we
design robust consensus protocols so that the agents can
achieve consensus despite the presence of the channel
uncertainties. Second and perhaps more importantly, we
investigate the fundamental limits of the uncertainties
under which consensus remains attainable. We address
these issues for two different communication topologies,
including undirected graphs and leader-follower graphs.
The following passages summarize our main contributions.

The mathematic preliminaries used in this paper are
summarized in Section 2. The uncertain communication
channel model is presented and the robust consensus
problem is formulated in Section 3. The robust consensus problem in the presence of stochastic channel uncertainties is studied in Section 4. The uncertain input
channel model is discussed in Section 5. Numerical simulation results are presented for illustration in Section
6. Finally, Section 7 concludes our paper.

We formulate and solve the robust consensus problem
in the mean square sense. Here we say that a group of
agents achieve mean square consensus if the states of the
agents converge asymptotically to a common state under the mean square criterion. We derive sufficient conditions guaranteeing the mean square consensus, under
which accordingly, a robust consensus protocol is designed based on the relative state information; the latter is achieved by solving a modified algebraic Riccati
equation. This result sheds important light into the intrinsic limit to the channel uncertainty variance that
a multi-agent system can tolerate to achieve consensus
with the given graph topology and the feedback protocol, which is seen to depend on the graph synchronizability, the topological entropy of the agents, and the
uncertainty variance. Interestingly, the condition recovers the conventional results on consensus of discrete-time
linear multi-agent systems with ideal channels in, e.g.,
[19,20,21], which is both necessary and sufficient in the
noise-free case.

2
2.1

Mathematical Preliminaries
Notations

The notations used in this paper are standard. Rn×m
denotes the set of n × m real matrices. The symbol 1
denotes a column vector with all entries equal to 1. kxk
denotes the 2-norm of a vector x and kAk denotes the
induced 2-norm of a real matrix A. The matrix inequality
A > B means A and B are symmetric matrices and
A−B is positive definite. A⊗B represents the Kronecker
product of matrices A and B. The expectation operator
is denoted by E{·}.
2.2

A further expansion of these results concerns the case
where uncertainties are present in the control input
channels of the agents. In this case, each agent communicates with its neighbors through the same communica-

Algebraic Graph Theory

This subsection summarizes some relevant facts on
graph theory, which are mainly adopted from [27,4].

2

paper we model each communication channel as an ideal
transmission system subject to a multiplicative stochastic uncertainty. Specifically, each agent obtains the relative state information from its neighbors through uncertain channels, which are ideal channels with a unity
transfer function perturbed by an stochastic uncertainty
∆ij , as shown in Fig. 1.

A directed graph G is defined by G = (V, E), where V =
{1, · · · , N } is the set of nodes and E ⊆ V × V denotes
the set of edges. For an edge (vi , vj ), node vi is called
the parent node (i.e., the head), vj is the child node
(i.e., the tail), and vi is a neighbor of vj . A graph with
the property that (vi , vj ) ∈ E implies that (vj , vi ) ∈ E
for any vi , vj ∈ V, i.e., each edge is an unordered pair
of nodes, is said to be undirected. A path from node i1
to node il is a sequence of ordered edges in the form of
(ik , ik+1 ), k = 1, · · · , l − 1. A directed graph contains
a directed spanning tree if there exists a node called
the root which has directed paths to all other nodes in
the graph. For a directed graph G, its adjacency matrix,
denoted by A = [aij ] ∈ RN ×N , is defined such that
aii = 0, aij is a positive value if (vj , vi ) ∈ E and aij =
0 otherwise, where aij denotes the weight for the edge
(vj , vi ) ∈ E. For an undirected graph, assume that each
of its edges has a head and a tail. The incidence matrix
associated with the undirected graph, denoted by D =
[dij ] ∈ R|V|×|E|, is defined as dij = −1 if vi is the tail of
(vi , vj ), dij = 1 if vi is the head of (vi , vj ), and dij = 0
otherwise. The Laplacian matrix L = [Lij ] ∈ RN ×N
PN
associated with a graph G is defined as Lii = j=1 aij
and Lij = −aij , i 6= j.

ܽ௜௝ ሺ‫ݔ‬௝ െ ‫ݔ‬௜ ሻ

agent j

The control input of each agent, i.e., the consensus protocol, is designed as
ui (k) = α

aij [1+∆ij (k)]K[xi (k)−xj (k)], i = 1, · · · , N,

(2)
where α ∈ R is a positive scaling factor, K ∈ R1×n is
the feedback gain matrix, aij denotes the (i, j)-th entry
of the non-weighted (i.e., aij ∈ {0, 1}) adjacency matrix
of the graph G, and ∆ij (k) ∈ R denotes the stochastic
uncertainty associated with the communication channel
between agents i and j.
We assume that the stochastic uncertainties ∆ij (k) satisfy the following assumption.
Assumption 2 ∆ij (k), (i, j) ∈ E in (2) are white noise
processes, independent from each other and for each k,
2
.
with E{∆ij (k)} = 0 and E{∆2ij (k)} = σij

Stochastically Perturbed Channels and Problem Formulation

Consider a network consisting of N discrete-time linear
agents. The dynamics of the i-th agent are described by
i = 1, · · · , N,

N
X
j=1

Lemma 2 ([1]) Zero is an eigenvalue of L with 1 as a
right eigenvector and all nonzero eigenvalues have positive real parts. Besides, zero is a simple eigenvalue of L
if and only if G has a directed spanning tree.

xi (k + 1) = Axi (k) + Bui (k),

agent i

Fig. 1. An uncertain communication channel between agents
i and j.

Lemma 1 ([27]) For an undirected graph, L =
DW DT , where W is an |E| × |E| diagonal matrix, with
positive aij on the diagonal.

3

ο௜௝

Remark 1 The stochastically perturbed communication channel in this paper is fairly general and can be
used to describe several communication losses in digital networks, such as quantization [17], signal distortion
[9], packet drop [18], and multiplicative (relative-statedependent) communication noises [13]. Specifically, the
binary i.i.d. packet loss and Rice fading channel [18] can
be described by a structured bounded variance uncertainty in the form of (2). It is also shown in [17] that
if ∆ij (k) is uniformly distributed over a certain interval
for every i, j, and k, then the uncertainty ∆ij (k) can be
viewed as a random quantization error.

(1)

where xi ∈ Rn is the state vector and ui ∈ R is the
control input vector of the i-th agent, respectively, and
the following assumption holds.
Assumption 1 The pair (A, B) is stabilizable.
The information flow among the N agents is depicted by
a graph G, which can be either directed or undirected.
Agent j can obtain information from agent i, if (i, j) is
an edge. The graph G merely depicts the information
flow topology among the agents. In practice, the agents
cooperate via information exchange over a network of
communication channels, which in general are subject to
transmission errors resulted from communication noises
and channel constraints. Motivated by the random quantizers in [17] and the fading channel model in [18], in this

The protocol (2) solves the robust consensus problem in
the mean square sense, i.e., the mean square consensus
problem, in the presence of the uncertain channel model
described as above, if limk→∞ E{kxi (k) − xj (k)k2 } = 0,
i, j = 1, · · · , N . Our objective in this paper is two-fold.
We first determine conditions such that the agents in
(1) will achieve consensus under the protocol (2). This

3

Lemma 3 ([28]) Assume that (A, B) be stablizable and
B ∈ Rn . Then, the MARE (5) has a unique positivedefinite solution P , if |δ̆| < 1/M (A), where M (A) ,
Q
n
i=1 max{1, |λi (A)|} denotes the Mahler measure of A,
which is the absolute value of the product of the unstable
eigenvalues of A.

in turn leads to intrinstic limits relating the channel uncertainty specification to the network synchronizability
and the agents’ unstable dynamics. Next, we design the
feedback gain matrix K in (2) such that the states of the
agents reach agreement in the mean square sense.
4

Consensus over Uncertain Communication
Channels

The following theorem presents a sufficient condition to
solve the mean square consensus problem.

In this section, we consider the robust consensus problem with the stochastically perturbed channel model for
different network topologies.
4.1

Theorem 4 Suppose that Assumptions 1–3 hold. There
exists a consensus protocol in the form of (2) solving the
mean square consensus problem for the agents in (1), if
the following condition holds:

Undirected Graphs

2
(αλi − 1)2 + α2 σmax
λi <

In this subsection, we consider the case where the communication graph G is undirected, which satisfies the
following assumption.

Let x(k) = [x1 (k)T , · · · , xN (k)]T . Then, it follows from
(1) and (2) that the closed-loop network dynamics can
be written as

Proof
Because Assumption 3 holds, it follows
from Lemma 2 that zero is a simple eigenvalue
of L and all the other eigenvalues are positive.
Let U ∈ RN ×N be a unitary matrix such that
U T LU = Λ , diag(0, λ2 , · · · , λN ). Since the right and
left eigenvectors of L corresponding to the zero eigenvalue are 1 and 1T , respectively, we select U = [ √1N Y1 ],
where Y1 ∈ RN ×(N −1) . It is not difficult to check that

(3)

where Π(k) = [Πij (k)]N ×N ∈ RN ×N , with Πij (k) =
PN
−aij ∆ij (k), i 6= j, and Πii (k) = j=1 aij ∆ij (k), and
L is the symmetric Laplacian matrix associate with G.
Evidently, Π(k)1 = 0.

Y1T Y1 = IN −1 , Y1 Y1T = M,

Let ξ(k) = (M ⊗ In )x(k), where M , IN − N1 11T . It
is easy to see that 0 is a simple eigenvalue of M with
1 as the eigenvector and 1 is the other eigenvalue with
multiplicity N − 1. Then, it follows that ξ(k) = 0 if and
only if x1 (k) = · · · = xN (k). Hereafter, we will refer
to ξ(k) as the consensus error. In light of the facts that
LM = M L = L and Π(k)M = Π(k), we can deduce
from (3) that ξ(k) satisfies the following dynamics:
ξ(k + 1) = (IN ⊗ A + αL ⊗ BK)ξ(k)
+ α(M ⊗ B)Π(k)(IN ⊗ K)ξ(k),

(6)

2
2
2
where σmax
, max(i,j)∈E {σij
+ σji
} and λ2 ≤ · · · ≤ λN
are the nonzero eigenvalues of L. Furthermore, the
feedback gain matrix K in (2) can be chosen as
K = −(B T P B)−1 B T P A, where P > 0 is the unique
solution to the MARE (5) with maxi=2,N {(αλi − 1)2 +
2
α2 σmax
λi } ≤ δ̆ 2 < 1/M (A)2 .

Assumption 3 The graph G is undirected and connected.

x(k + 1) = (IN ⊗ A + αL ⊗ BK)x(k)
+ α(IN ⊗ B)Π(k)(IN ⊗ K)x(k),

1
, i = 2, N,
M (A)2

Y1T LY1 = Λ1 , diag(λ2 , · · · , λN ).

(7)

T
Let ξ̃(k) , [ξ˜1 (k)T , · · · , ξ̃N
(k)]T = (U T ⊗In )ξ(k). Then,
(4) can be rewritten into

˜ + 1) = (IN ⊗ A + αΛ ⊗ BK)ξ(k)
˜
ξ(k
˜
+ α(U T M ⊗ B)Π(k)(U ⊗ K)ξ(k).

(8)

˜
In virtue of the definitions of ξ(k) and ξ(k),
we can verify
T
1
that ξ̃1 (k) = ( √N ⊗ In )ξ(k) ≡ 0. Therefore, the mean
square consensus problem is reduced to checking the
T
T
˜
˜T
mean square stability
h
iof ζ(k) , [ξ2 (k) , · · · , ξN (k)] .

(4)

Evidently, the consensus protocol (2) solves the mean
square consensus problem for the agents in (1), if the
system (4) is mean square stable.

Since U T M =
lows that

Before moving forwards, we introduce the following
modified algebraic Riccati equation (MARE) [28]:

0
Y1T M

and Π(k)U = [ 0 Π(k)Y1 ], it fol-

(U T M ⊗ B)Π(k)(U ⊗ K)
= diag(0, (I ⊗ B)(Y1T Π(k)Y1 )(I ⊗ K)),

P = AT P A−(1− δ̆ 2 )AT P B(B T P B)−1 B T P A+Q, (5)

where we have used the fact that Y1T M = Y1 , which
follows readily from (7). Then, we can derive from (8)

where P ≥ 0, Q > 0, and δ̆ ∈ R. The lemma given below
concerns the existence of a solution to the MARE (5).

4

By invoking (15), it follows that (11) holds, if M > 0,
where

that ζ(k) satisfies
ζ(k + 1) =(I ⊗ A + αΛ1 ⊗ BK)ζ(k) + α(I ⊗ B)

M =I ⊗ P − (I ⊗ AT + αΛ1 ⊗ K T B T )(I ⊗ P )(I ⊗ A

(9)

× (Y1T Π(k)Y1 )(I ⊗ K)ζ(k).

2
+ αΛ1 ⊗ BK) − α2 σmax
Λ1 ⊗ K T B T P BK.

(16)
Since the matrices on the right side of (16) are block
diagonal, it is evident that M > 0, if

By using a slightly modified version of Theorem 6.4 in
[18] or the result in Section 9.1.1 in [29], the system (9)
in mean square stable if and only if there exists a P > 0
such that
T

T

P > (A + αλi BK)T P (A + αλi BK)
2
+ α2 σmax
λi K T B T P BK, i = 2, · · · , N.

T

P − (I ⊗ A + αΛ1 ⊗ K B )P(I ⊗ A − αΛ1 ⊗ BK)
− α2 (I ⊗ K T )E{Y1T Π(k)T Y1 (I ⊗ B T )P

Substituting K = −(B T P B)−1 B T P A into (17) and invoking (6) yield

× (I ⊗ B)Y1T Π(k)Y1 }(I ⊗ K) > 0.
(10)
In the following, we will show that I ⊗ P , with P > 0
being the solution to the MARE (5), satisfies (10). With
P = I ⊗ P , the inequality (10) can be rewritten as

2
P − AT P A − [(αλi − 1)2 − 1 + σmax
α2 λi ]AT P B

× (B T P B)−1 B T P A
≥ P − AT P A + (1 − δ̆ 2 )AT P B(B T P B)−1 B T P A > 0,
(18)
2
where we have used the fact that (αλi −1)2 −1+σmax
α2 λi
is convex with respect to λi . In light of (17) and (18),
it follows from (16) that M > 0. Then, we obtain that
P = I ⊗ P satisfies (10), i.e., the system (9) is mean
square stable. Therefore, the consensus protocol (2) with
K chosen as above solves the mean square consensus
problem provided that the condition (6) holds.


I ⊗ P − (I ⊗ AT + αΛ1 ⊗ K T B T )(I ⊗ P )(I ⊗ A
+ αΛ1 ⊗ BK) − α2 E{Y1T Π(k)T Y1 Y1T Π(k)Y1 }
⊗ K T B T P BK > 0.
(11)
By noting that M ≤ I and in light of (7), we have
Y1T Π(k)T Y1 Y1T Π(k)Y1 = Y1T Π(k)T M Π(k)Y1
≤ Y1T Π(k)T Π(k)Y1 .

(12)

Remark 2 The scalar α in (2) is a design scaling
parameter, which is intended to regulate the left-hand
side of (6). By simple calculations, we can choose α =
2
such that left-hand side of (6) is minimized
2
λ2 +λN +σmax
2
for given λ2 , λN , and σmax
. In this case, the condition
(6) becomes

Under Assumption 2, it is not difficult to derive that the
expectation of Π(k)T Π(k) satisfies
E{Π(k)T Π(k)} = Θ,
2
2
θij = −aij (σij
+ σji
), i 6= j,
θii =

N
X

2
2
(λN − λ2 − σmax
)2 + 4σmax
λN
1
<
.
2
2
(λN + λ2 + σmax )
M (A)2

(13)

2
2
aij (σji
+ σij
), i = 1, · · · , N,

j=1

Θ = D∆DT ,
∆=

+

2
σij
, ∀(i, j)

∈ E) ∈ R

M×M

.

2
1
(λN − λ2 )2 + 4σmax
λN
<
.
(λN + λ2 )2
M (A)2

(20)

When the communication channels are noise-free, which
2
is equivalent to σij
= 0 for all i, j, the condition (19) or
1−λ2 /λN
1
(20) reduces to 1+λ
. The latter is the nec< M(A)
2 /λN
essary and sufficient condition for consensus with ideal
channels, obtained in, e.g., [19,20,21].

(14)

Then, we can derive from (12), (13), and (14) that

Remark 3 Theorem 4 uncovers the intrinsic constraints induced by the channel uncertainties, the communication topology, and the unstable dynamics of the
agents. The eigenratio λ2 /λN in (19) is commonly used
to indicate the synchronizability of dynamical networks

E{Y1T Π(k)T Y1 Y1T Π(k)Y1 }

2
≤ σmax
Y1T DDT Y1
2
= σmax Y1T LY1
2
= σmax
Λ1 .

(19)

On the other hand, If the variances of the channel uncertainties are not available, in this case we can choose
2
and the condition (6) becomes
α = λ2 +λ
N

where θij denotes the (i, j)-th entry of the matrix Θ
and we have also used the fact that aij = aji . It is not
difficult to verify that Θ corresponds to certain weighted
Laplacian matrix of the undirected graph G. Suppose
that there are M edges in the graph G and denote by
D ∈ RN ×M the incidence matrix of G. In light of Lemma
1, we can verify that

2
diag(σji

(17)

(15)

5

[30,31]. A larger eigenratio implies a better synchronizability. The Mahler measure M (A) of A, or the
topological entropy log2 M (A), plays an important role
in networked control systems [6,32], as it describes the
minimum data rate for stabilizing an unstable system.
2
The largest variance σmax
can be used to measure the
maximum mean square channel capacity for the stochastic communication channels, as discussed in [18]. As
demonstrated in the condition (19), the synchronizability factor, the topological entropy of A, and the mean
square channel capacity impose intrinsic limitations on
achieving consensus over stochastic uncertain channels.

Let ei (k) = xi (k) − x1 (k), i = 2, · · · , N . From (1) and
(2), we find that
ei (k+1) = Aei (k)+αB

aij [1+∆ij (k)]K[ei (k)−ej (k)],

j=1

(21)
where e1 = 0. Let e(k) = [e2 (k)T , · · · , eN (k)]T . Then,
we rewrite (21) into
e(k + 1) = (IN −1 ⊗ A + αL1 ⊗ BK)e(k)
(22)
b
+ α(IN −1 ⊗ B)Π(k)(I
N −1 ⊗ K)e(k),

Remark 4 For the case where the agents have no eigenvalues outside the unit circle, i.e., M (A) = 1, it is worth
noting that the condition (19) always holds and the consensus protocol (2) can be constructed as in Theorem 1
and Remark 2 to ensure mean square consensus for any
channel uncertainties satisfying Assumption 3 as long as
(A, B) is stabilizable. In this sense, the condition (19)
is both necessary and sufficient. Nevertheless, the conservatism of the condition (19) remains unclear for the
case of M (A) > 1. The condition (20) is generally not
necessary. For instance, consider a group of single integrators with a complete graph and assume for simplicity
that the variances of the channel uncertainties are all
equal, denoted by σ̄ 2 . In this case, the condition (20) becomes σ̄ 2 < N2 . In light of the frequency-domain meansquare small gain theorem in [18,33], a necessary and
sufficient condition to achieve mean square consensus is
that σ̄ 2 < 1 when N = 2, σ̄ 2 < 1.5 when N = 3, and
σ̄ 2 < 16/7 when N = 4. It is easy to verify that the
condition (20) is tight for the special cases with two or
three single-integrator agents with complete graphs, and
is conservative if N ≥ 4.
4.2

N
X

b
b ij (k)](N −1)×(N −1) , with Π
b ij (k) =
where Π(k)
= [Π
PN
b
−aij ∆ij (k), i 6= j, and Πii (k) = j=1 aij ∆ij (k). Evidently, xi (k), i = 2, · · · , N , approach x1 (k), if e(k) in
(22) converges to zero. Therefore, the consensus protocol (2) solves the mean square leader-follower consensus
problem for the agents in (1), if the system (22) is mean
square stable.
Theorem 5 Suppose that Assumptions 1, 2, and 4 hold.
Then there exists a consensus protocol (2) achieving
mean square consensus for the agents in (1), if
2
(αλi − 1)2 + α2 σ̃max
λi <

2
where σ̃max
,

max

i,j=2,··· ,N

1
, i = 2, N,
M (A)2

(23)

2
2
2
{σj1
, σij
+ σji
}.

Proof Similarly as in the proof of Theorem 4, the system
(22) is mean square stable, if the following inequality
holds:
(I ⊗ AT + αL1 ⊗ K T B T )(I ⊗ P )(I ⊗ A + αL1 ⊗ BK)
b T Π(k)}
b
− (I ⊗ P ) + α2 E{Π(k)
⊗ K T B T P BK < 0,
(24)
where K = −(B T P B)−1 B T P A and P > 0 is a solution
to the MARE (5) with δ̆ 2 lies within the left-hand and
right-hand sides of (23). Under Assumption 2, it is not
difficult to derive that

Leader-follower Graphs

In this subsection, we consider the case where there exists a leader. Without loss of generality, let the agent in
(1) indexed by 1 be the leader and the rest be the followers. The leader receives no information from any follower and only a subset of the followers have access to
the leader’s information. It is assumed that the leader’s
control input is equal to zero, i.e., u1 = 0, and the control
inputs of the followers are described by (2). We assume
that the communication graph G among the N agents
satisfies the following assumption.

b T Π(k)}
b
b ∈ R(N −1)×(N −1) ,
E{Π(k)
=Θ
2
2
θ̂ij = −aij (σij
+ σji
), i 6= j,

θ̂ii =

Assumption 4 The graph G contains a directed spanning tree with the leader as the root and the subgraph
Gs associated with the N − 1 followers is undirected.

N
X

2
[aij (σji

+

2
σij
)

+

2
],
aj1 σj1

(25)

i = 2, · · · , N,

j=2

b
where θ̂ij denotes the (i, j)-th entry of the matrix Θ.

Because the leader has no neighbors, the Laplacian matrix
with G can be partitioned
h L associated
i
0 01×(N −1)
as L = L2
, where L2 ∈ R(N −1)×1 and
L1

Without loss of generality, assume that the followers indexed by 2, · · · , q + 1, have access to the
leader. Further, suppose that there are M edges
in the graph G. Thus, there exist M − q edges in
the subgraph Gs among the N − 1 followers. Let

L1 ∈ R(N −1)×(N −1) . By Lemma 2 and Assumption 4,
it is clear that L1 > 0.

6

b
∆

=

2
2
2
2
, σji
+ σij
, ∀(i, j) ∈ Gs ),
diag(σ21
, · · · , σ(q+1)1
{z
}
{z
} |
|

channels. This is different from the undirected graph
case in the previous subsection.

M−q

q

where the last M −q items
to the M −q chanh correspond
i
nels in Gs . Define D = B̄ Ds , where Ds ∈ RN ×(M−q)
denotes the incidence matrix associated with Gs and
B̄ ∈ RN ×q is formed by the first q columns of IN .

5

In this section, we consider the case where the agents
in (1) are perturbed by uncertainties in their control input channels. The stablization problem of a single LTI
system with uncertain input channels has been considered in [32,34]. The uncertain input channel model is il˜ i (k) denotes the stochastic
lustrated in Fig. 2, where ∆
uncertainty in the input channel of agent i and vi (k) =
PN
j=1 aij K[xi (k) − xj (k)] denotes the signal available
to agent i, which will go through the uncertain input
channel for controller design. The stochastic uncertain˜ i (k) satisfy the following assumption.
ties ∆

We first show the following claim.
b defined as in (25), is equal to
Claim 1 The matrix Θ,
T
b
D∆D
.

2
2
b 1 = diag(σ21
b2 =
Let ∆
, · · · , σ(q+1)1
) ∈ Rq×q and ∆
2
2
diag(σji
+ σij
, ∀(i, j) ∈ Gs ) ∈ R(M−q)×(M−q) . Denote
by Ls the weighted Laplacian matrix corresponding to
the undirected subgraph Gs , which, in virtue of Lemma
b 2 DsT . Then,
1, is equal to Ds ∆

#" #
"
h
i ∆
b1 0
B̄ T
T
b
D ∆D = B̄ Ds
b 2 DsT
0 ∆

b 2 DsT
b 1 B̄ T + Ds ∆
= B̄ ∆
2
2
= diag(σ21
, · · · , σ(q+1)1
, 0, · · · , 0) + Ls .

˜ i (k), i = 1, · · · , N , in (29) are indeAssumption 5 ∆
pendent zero-mean white noise processes with variances
σ̃i2 .

(26)
‫ݒ‬௜

b it is not difficult to verify that
By the definition of Θ,
b
the right hand of the last equation in (26) is equal to Θ.
T

ο෨௜

‫ݑ‬௜

Fig. 2. The uncertain input channel for agent i.

In this section, for simplicity we only consider the case
where the communication graph G is undirected and satisfies Assumption 3. The consensus protocol is given as
follows:

In light of Claim 1, it follows from (25) that

2
b
b T Π(k)}
b
≤ σ̃max
DD
E{Π(k)
= D∆D
2
= σ̃max L1 .

Consensus via Uncertain Input Channels

T

(27)

ui (k) = α

T

Note that DD = L1 is a direct consequence of Claim 1
b = I. In light of (27), we know that (24) holds, if
with ∆

N
X

˜ i (k)]K[xi (k)−xj (k)], i = 1, · · · , N,
aij [1+∆

j=1

(29)

where aij , α, and K are defined as in (2).

(I ⊗ AT + αL1 ⊗ K T B T )(I ⊗ P )(I ⊗ A + αL1 ⊗ BK)

This uncertain input channel model is related to the
uncertain communication channel in the previous sections. By comparing (29) to (2), we can observe that the
uncertain input channel model can be regarded in the
sense that each agent communicates with its neighbors
through the same communication channel perturbed by
˜ i (k). The uncertain
a multiplicative uncertainty 1 + ∆
channels are different for different agents, even though
the agents may have bidirectional communication links.
This differs from the uncertain communication channel
model in the previous sections.

2
− (I ⊗ P ) + α2 σ̃max
L1 ⊗ K T B T P BK < 0.

(28)
Following similar steps in the proof of Theorem 4, it is
not difficult to show that if the condition (23) holds,
then (28) and also (24) hold, implying that (22) is mean
square stable, i.e., the consensus protocol (2) solves the
mean square leader-follower consensus problem. The details are omitted here for conciseness.

Remark 5 For the leader-follower graphs considered in
this subsection, communications among the followers are
bidirectional, while those between the followers and the
leader are directional. Therefore, it is reasonable to define the maximum mean square channel capacity in this
case by the maximum of the sum of the variances of the
stochastic uncertainties on every bidirectional channel
and the variances of the uncertainties on the directional

Let x(k) = [x1 (k)T , · · · , xN (k)T ]T . It then follows from
(1) and (29) that x(k) in this case satisfies
e
x(k+1) = [I ⊗A+αL⊗BK +α(I ⊗B)∆(k)(L⊗K)]x(k),
(30)
7

e
˜ 1 (k), · · · , ∆
˜ N (k)) and L is the
where ∆(k)
, diag(∆
Laplacian matrix of G.

12

10

8

The following theorem ensures that (29) solves the mean
square consensus problem.

6

4

2

Theorem 6 Suppose that Assumptions 1, 2, and 5 hold.
The consensus protocol (29) solves the mean square consensus problem for the agents in (1), if

0

-2

-4

(31)

Since LM = M L and both M and L have zero row and
column sums, we can choose U2 , [ √1N Y2 ] ∈ RN ×N ,
with Y2 ∈ RN ×(N −1) , be the unitary matrix such that
c , diag(0, IN −1 ) and U2T LU2 = Λ ,
U2T M U2 = M
ˇ
diag(0, Λ1 ), where Λ1 = diag(λ2 , · · · , λN ). Let ξ(k)
,
T
T
T
T
ˇ
[ξˇ1 (k) , · · · , ξ̌N (k)] = (U
⊗
I
)ξ(k),
where
ξ
(k)
=
0.
n
1
h2
i
0
0
T
c
T
Since M U2 ∆(k)U2 Λ =
, we can derive

7

30

40

50

60

Conclusions

In this paper we have studied a robust consensus problem
for a network of general discrete-time linear agents coordinating through uncertain communication channels.
We model the communication channel as an ideal transmission system subject to a multiplicative stochastic
perturbation. We have presented sufficient robust consensus conditions, which exhibit intrinstic limitations
imposed by the synchronizability factor, the topological entropy of the agents, and the mean square channel
capacity. Under this limit, consensus protocols can be
designed by solving an MARE.

0 Y2 ∆(k)Y2 Λ1
T
, ξˇN
(k)]T satisfies

ζ̌(k + 1) = (I ⊗ A + αΛ ⊗ BK)ζ̌(k)
+ α(I ⊗ B)Y2T ∆(k)Y2 Λ1 (I ⊗ K)ζ̌(k).
(32)
The rest of the derivations can be completed by following
steps in the proof of Theorems 4, by further noting that
E{Λ1 Y2T ∆(k)Y2 Y2T ∆(k)Y2 Λ1 } ≤ E{Λ1 Y2T ∆(k)2 Y2 Λ1 }
≤ ̺2 Λ21 ,

References

where we have used the facts that Y2 Y2T = M and
Y2T Y2 = I. The details are omitted here for brevity. 
6

20

4 that the feedback gain matrix of (2) is obtained as
K = − [ 0.1038 1.1038 ]. The initial states of the agents
2
are
to be x1 (0) = [ 10 ], x2 (0) = −1
, x3 (0) =

 −1 chosen
0.8
2
,
x
(0)
=
[
],
x
(0)
=
[
],
and
x
(0)
=
[ 01 ]. The
4
5
6
2
3
0.5
average of 1000 sample trajectories of the relative states
xi (k) − x1 (k), i = 2, · · · , 6, under (2) with α = 0.25
and K designed as above, are depicted in Fig. 3, which
is an approximation of the expectation of xi (k) − x1 (k)
and from which it can be observed that mean square
consensus is indeed achieved.

Proof Let the consensus error ξ(k) be defined as in (4).
We can verify that ξ(k) in this case satisfies

that ζ̌(k) , [ξˇ2 (k)T , · · ·

10

Fig. 3. The average of the sampled trajectories of
xi (k) − x1 (k), i = 2, · · · , 6.

where ̺2 , max σ̃i2 .

ξ(k + 1) = (I ⊗ A + αL ⊗ BK)ξ(k)
+ α(M ⊗ B)∆(k)L(I ⊗ K)ξ(k),

0

k

1
(αλi − 1)2 + α2 ̺2 λi <
, i = 2, N,
M (A)2

[1] W. Ren and R. W. Beard, Distributed Consensus in Multivehicle Cooperative Control. Springer, 2008.
[2] R. Olfati-Saber, J. Fax, and R. Murray, “Consensus and
cooperation in networked multi-agent systems,” Proceedings
of the IEEE, vol. 95, no. 1, pp. 215–233, 2007.

Numerical Simulations

[3] G. Antonelli, “Interconnected dynamic systems: An overview
on distributed control,” IEEE Control Systems Magazine,
vol. 33, no. 1, pp. 76–88, 2013.

Consider a group of six discrete-time double integrators,
i.e., the matrices in (1) are given by A = [ 10 11 ], B = [ 01 ] .
The communication graph is an undirected cycle, where
the communication channels are perturbed by stochastic
uncertainties satisfying Assumption 2. The smallest and
largest nonzero eigenvalues of the Laplacian matrix are
1 and 4, respectively. For illustration, let the variances
of the uncertainties of the six channels be 1.5. Solving
the MARE (3) with Q = 3I and δ̆ 2 = 0.9 gives P =
0.1521
103 × [ 0.0319
0.1521 1.4643 ]. Therefore, it follows from Theorem

[4] Z. Li and Z. Duan, Cooperative Control of Multi-Agent
Systems: A Consensus Region Approach. Boca Raton, FL:
CRC Press, 2014.
[5] G. Goodwin, D. Quevedo, and E. Silva, “An introduction
to networked control systems,” in Proc. 6th Asian Control
Conference, Bali, Indonesia, pp. 50–74.
[6] G. N. Nair, F. Fagnani, S. Zampieri, and R. J. Evans,
“Feedback control under data rate constraints: An overview,”
Proceedings of the IEEE, vol. 95, no. 1, pp. 108–137, 2007.

8

[25] Y. Long, S. Liu, and L. Xie, “Distributed consensus of
discrete-time multi-agent systems with multiplicative noises,”
International Journal of Robust and Nonlinear Control,
vol. 25, no. 16, pp. 3113–3131, 2015.

[7] J. P. Hespanha, P. Naghshtabrizi, and Y. Xu, “A survey of
recent results in networked control systems,” Proceedings of
the IEEE, vol. 95, no. 1, p. 138, 2007.
[8] S. Tatikonda and S. Mitter, “Control under communication
constraints,” Automatic Control, IEEE Transactions on,
vol. 49, no. 7, pp. 1056–1068, 2004.

[26] H. L. Trentelman, K. Takaba, and N. Monshizadeh, “Robust
synchronization of uncertain linear multi-agent systems,”
IEEE Transactions on Automatic Control, vol. 58, no. 6,
pp. 1511–1523, 2013.

[9] J. H. Braslavsky, R. H. Middleton, and J. S. Freudenberg,
“Feedback stabilization over signal-to-noise ratio constrained
channels,” IEEE Transactions on Automatic Control, vol. 52,
no. 8, pp. 1391–1403, 2007.

[27] M. Mesbahi and M. Egerstedt, Graph Theoretic Methods in
Multiagent Networks. Princeton University Press, 2010.
[28] L. Schenato, B. Sinopoli, M. Franceschetti, K. Poolla, and
S. Sastry, “Foundations of control and estimation over lossy
networks,” Proceedings of The IEEE, vol. 95, no. 1, pp. 163–
187, 2007.

[10] G. N. Nair and R. J. Evans, “Stabilization with data-ratelimited feedback: tightest attainable bounds,” Systems &
Control Letters, vol. 41, no. 1, pp. 49–56, 2000.
[11] R. Carli, F. Fagnani, A. Speranzon, and S. Zampieri,
“Communication constraints in the average consensus
problem,” Automatica, vol. 44, no. 3, pp. 671–684, 2008.

[29] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan,
Linear Matrix Inequalities in System and Control Theory.
Philadelphia, PA: SIAM, 1994.

[12] T. Li, M. Fu, L. Xie, and J. Zhang, “Distributed consensus
with limited communication data rate,” IEEE Transactions
on Automatic Control, vol. 56, no. 2, pp. 279–292, 2011.

[30] Z. Duan, G. Chen, and L. Huang, “Complex network
synchronizability: Analysis and control,” Physical Review E,
vol. 76, no. 5, p. 56103, 2007.

[13] T. Li, F. Wu, and J.-F. Zhang, “Multi-agent consensus
with relative-state-dependent measurement noises,” IEEE
Transactions on Automatic Control, vol. 59, no. 9, pp. 2463–
2468, 2014.

[31] L. Pecora and T. Carroll, “Master stability functions for
synchronized coupled systems,” Physical Review Letters,
vol. 80, no. 10, pp. 2109–2112, 1998.

[14] L. Cheng, Z.-G. Hou, M. Tan, and X. Wang, “Necessary and
sufficient conditions for consensus of double-integrator multiagent systems with measurement noises,” Automatic Control,
IEEE Transactions on, vol. 56, no. 8, pp. 1958–1963, 2011.

[32] L. Qiu, G. Gu, and W. Chen, “Stabilization of networked
multi-input systems with channel resource allocation,” IEEE
Transactions on Automatic Control, vol. 58, no. 3, pp. 554–
568, 2013.

[15] F. Fagnani and S. Zampieri, “Average consensus with
packet drop communication,” SIAM Journal on Control and
Optimization, vol. 48, no. 1, pp. 102–133, 2009.

[33] J. Lu and R. E. Skelton, “Mean-square small gain theorem for
stochastic control: discrete-time case,” IEEE Transactions
on Automatic Control, vol. 47, no. 3, pp. 490–494, 2002.

[16] J. Wu and Y. Shi, “Average consensus in multi-agent systems
with time-varying delays and packet losses,” in The 2012
American Control Conference, pp. 1579–1584, IEEE, 2012.

[34] N. Xiao, L. Xie, and L. Qiu, “Feedback stabilization of
discrete-time networked systems over fading channels,” IEEE
Transactions on Automatic Control, vol. 57, no. 9, pp. 2176–
2189, 2012.

[17] N. Xiao, L. Xie, and L. Qiu, “Mean square stabilization of
multi-input systems over stochastic multiplicative channels,”
in Proceedings of the 48th IEEE Conference on Decision and
Control and the 28th Chinese Control Conference, pp. 6893–
6898, 2009.
[18] N. Elia, “Remote stabilization over fading channels,” Systems
& Control Letters, vol. 54, no. 3, pp. 237–249, 2005.
[19] Z. Li, Z. Duan, and G. Chen, “Consensus of discrete-time
linear multi-agent systems with observer-type protocols,”
Discrete and Continuous Dynamical Systems-Series B,
vol. 16, no. 2, pp. 489–505, 2011.
[20] K. You and L. Xie, “Network topology and communication
data rate for consensusability of discrete-time multi-agent
systems,” IEEE Transactions on Automatic Control, vol. 56,
no. 10, pp. 2262–2275, 2011.
[21] K. Hengster-Movric, K. You, F. L. Lewis, and L. Xie,
“Synchronization of discrete-time multi-agent systems on
graphs using riccati design,” Automatica, vol. 49, no. 2,
pp. 414–423, 2013.
[22] J. Wang and N. Elia, “Distributed averaging under
constraints on information exchange: emergence of lévy
flights,” IEEE Transactions on Automatic Control, vol. 57,
no. 10, pp. 2435–2449, 2012.
[23] D. Zelazo and M. Bürger, “On the robustness of uncertain
consensus networks,” arXiv preprint arXiv:1408.4471, 2014.
[24] X. Ma and N. Elia, “Mean square performance and robust yet
fragile nature of torus networked average consensus,” IEEE
Transactions on Control of Network Systems, vol. 2, no. 3,
pp. 216–225, 2015.

9

