1

Pull-Based Distributed Event-triggered Consensus for Multi-agent
Systems with Directed Topologies

arXiv:1410.4246v2 [math.OC] 24 Apr 2015

Xinlei Yi, Wenlian Lu and Tianping Chen

Abstract—This paper mainly investigates consensus problem
with pull-based event-triggered feedback control. For each
agent, the diffusion coupling feedbacks are based on the states
of its in-neighbors at its latest triggering time and the next
triggering time of this agent is determined by its in-neighbors’
information as well. The general directed topologies, including
irreducible and reducible cases, are investigated. The scenario
of distributed continuous communication is considered firstly.
It is proved that if the network topology has a spanning tree,
then the event-triggered coupling strategy can realize consensus
for the multi-agent system. Then the results are extended
to discontinuous communication, i.e., self-triggered control,
where each agent computes its next triggering time in advance
without having to observe the system’s states continuously.
The effectiveness of the theoretical results are illustrated by a
numerical example finally.
Keywords: Directed, irreducible, reducible, consensus, multiagent systems, event-triggered, self-triggered.

I. I NTRODUCTION
Consensus problem in multi-agent systems has been widely
and deeply investigated. The basic idea of consensus lies in
that each agent updates its state based on its own state and the
states of its neighbors in such a way that the final states of all
agents converge to a common value [1]. The model normally
is of the following form:
ẋ(t) = −Lx(t)

(1)

where the column vector x(t) consists of all nodes’ states and
L is the corresponding weighted Laplacian matrix. There are
many results reported in this field [1]-[4] and the references
therein. In these researches, the network topologies vary from
fixed topologies to stochastically switching topologies, and
the most basic condition to realize a consensus is that the
underlying graph of the network system has a spanning tree.
In recent years, with the development of sensing, communications, and computing equipment, event-triggered control
[5]-[9] and self-triggered control [10]-[14] have been proposed
and studied. Instead of using the continuous state to realize
a consensus, the control in event-triggered control strategy is
Xinlei Yi is with the School of Mathematical Sciences, Fudan University;
Wenlian Lu (corresponding author) is with the Centre for Computational
Systems Biology and School of Mathematical Sciences, Fudan University,
and Department of Computer Science, The University of Warwick, Coventry,
United Kingdom; Tianping Chen is with the School of Computer Science and
School of Mathematical Sciences, Fudan University, Shanghai 200433, China
(email: {yix11, wenlian, tchen}@fudan.edu.cn).
This work is jointly supported by the Marie Curie International Incoming
Fellowship from the European Commission (FP7-PEOPLE-2011-IIF-302421),
the National Natural Sciences Foundation of China (Nos. 61273211 and
61273309), and the Program for New Century Excellent Talents in University
(NCET-13-0139).

piecewise constant between the triggering times which need to
be determined. Self-triggered control is a natural extension of
the event-triggered control since the derivative of the concern
multi-agent system’s state is piecewise constant, which is very
easy to work out solutions (agents’ states) of the system. In
particular, each agent predicts its next triggering time at the
previous one. Inspired by above idea of event-triggered control
and self-triggered control, [17]-[25] considered the consensus
problem for multi-agent systems with event-triggered control.
In particular, in [17], under the condition that the graph is
undirected and strongly connected, the authors provide eventtriggered and self-triggered approaches in both centralized
and distributed formulations. It should be emphasized that the
approaches cannot be applied to directed graph. In [18], the
authors investigate the average-consensus problem of multiagent systems with directed and weighted topologies, but they
need an additional assumption that the directed topology must
be balanced. In [20], the authors propose a new combinational
measurement approach to event design, which will be used in
this paper.
In this paper, continuing with previous works, we study
event-triggered and self-triggered consensus in multi-agent
system with directed, reducible (irreducible) and weighted
topology.
Consider the following continuous-time linear multi-agent
system with discontinuous diffusions as follows
(
ẋi (t) = ui (t)
Pm
(2)
ui (t) = − j=1 Lij xj (tiki (t) ), i = 1, · · · , m

where ki (t) = arg maxk {tik ≤ t}, the increasing time
sequence {tjk }∞
k=1 , j = 1, · · · , m, which is named as trigger
times, is agent-wise and normally assuming tj1 = 0, for all
j ∈ I, where I = {1, 2, · · · , m}. We say agent vi triggers
at time tik means agent vi renews its control value at time
tik and sends tik , xi (tik ) and ui (tik ) to all its out-neighbours
immediately. At each tik , each agent vi “pulls” xj (tik ) from
agent vi if Lij 6= 0. (This does not mean that agent vi
has to send a request to its in-neighbours at tik in order to
get its in-neighbours’ states at tik . Instead, in event-triggered
control, agent vi ’s in-neighbours has to send its state to agent
vi continuously. And we will also give an algorithm to avoid
such continuous communication later.) In order to distinguish
it from others, we name this sort of feedback as pull-based.
Let us recall the model
xi (t + 1) = f (xi (t)) + ci

m
X
j=1

aij (f (xj (t)))

2

where ṡ(t) = f (s(t)) is a chaotic oscillator. It was proposed
and investigated in [15] for synchronization of chaotic systems.
It can also be considered as nonlinear consensus model.
As a special case, let f (x(t)) = x(t) and ci = (tik+1 − tik ),
then
m
X
xi (tik+1 ) = xi (tik ) + (tik+1 − tik )
aij xj (tjk )
j=1

which is just the event triggering (distributed) model for
consensus problem, though the term ”event triggering” was
not used. In centralized control, the bound for (tik+1 − tik ) =
(tk+1 − tk ) to reach synchronization was given in that paper
when the coupling graph is indirected (or in [16] for direct
graph), too.
In this paper, the distributed continuous monitoring with
pull-based feedback as the event-triggered controller is considered firstly, namely agent can observe its in-neighbours’
continuous states by its in-neighbours sending their continuous
states to it. It is proved that if the directed network topology
is irreducible, then the pull-based event-triggered coupling
strategy can realize consensus for the multi-agent system.
Then we generalize it to the reducible case. By mathematical
induction, it is proved that if the network topology has a
spanning tree, then the pull-based event-triggered coupling
strategy can realise consensus for the multi-agent system, too.
Finally the results are extended to discontinuous monitoring,
where each agent computes its next triggering time in advance
without having to receive the system’s state continuously (selftriggered).
In comparison to literature, we have three main contributions: (i) different from [17]-[22] and [25], we investigate
directed topologies, including irreducible and reducible cases,
and we do not make assumption that they are balanced;
(ii) different from [19], [22] and [23], the event-triggered
principles in our paper are fully distributed in the sense that
each agent only needs its in-neighbours’ state information,
especially does not need any a priori knowledge of any global
parameter and the Zeno behaviour can be excluded; (iii)
different from [18]-[23], we propose self-triggered principle,
by which continuous communication between agents can be
avoided.
The paper is organized as follows: in Section II, some
necessary definitions and lemmas are given; in Section III, the
pull-based event-triggered consensus in multi-agent systems
with directed topologies is discussed; in Section IV, the selftriggered formulation of the frameworks provided in Section
III is presented; in Section V, one numerical example is
provided to show the effectiveness of the theoretical results;
the paper is concluded in Section VI.
II. P RELIMINARIES
In this section we first review some relating notations,
definitions and results on algebraic graph theory [26], [27]
which will be used later in this paper.
Notions: k · k represents the Euclidean norm for vectors or the
induced 2-norm for matrices. 1 denotes the column vector with
each component 1 with proper dimension. ρ(·) stands for the

spectral radius for matrices and ρ2 (·) indicates the minimum
positive eigenvalue for matrices having positive eigenvalues.
Given two symmetric matrices M, N , M > N (or M ≥ N )
means M − N is a positive definite (or positive semi-definite)
matrix.
For a weighted directed graph (or digraph) G = (V, E, A)
with m agents (vertices or nodes), the set of agents V =
{v1 , · · · , vm }, set of links (edges) E ⊆ V × V, and the
weighted adjacency matrix A = (aij ) with nonnegative
adjacency elements aij > 0. A link of G is denoted by
e(i, j) = (vi , vj ) ∈ E if there is a directed link from
agent vj to agent vi with weight aij > 0, i.e. agent vj
can send information to agent vi while the opposite direction
transmission might not exist or with different weight aji . The
adjacency elements associated with the links of the graph are
positive, i.e., e(i, j) ∈ E ⇐⇒ aij > 0, for all i, j ∈ I. It is
assumed that aii = 0 for all i ∈ I. Moreover, the in- and outneighbours set of agent vi are defined as
Niin = {vj ∈ V | aij > 0},

Niout = {vj ∈ V | aji > 0}

The in- and out- degree of agent vi are defined as follows:
deg in (vi ) =

m
X

aij ,

j=1

deg out (vi ) =

m
X

aji

j=1

The degree matrix of digraph G is defined as D =
diag[deg in (v1 ), · · · , deg in (vm )]. The weighted Laplacian matrix associated with the digraph G is defined as L = D − A.
A directed path from agent v0 to agent vk is a directed graph
with distinct agents v0 , ..., vk and links e0 , ..., ek−1 such that
ei is a link directed from vi to vi+1 , for all i < k.
Definition 1: We say a directed graph G is strongly connected if for any two distinct agents vi , vj , there exits a
directed path from vi to vj .
By [27], we know that strongly connectivity of G is equivalent to the corresponding Laplacian matrix L is irreducible.
Definition 2: We say a directed graph G has a spanning tree
if there exists at least one agent vi0 such that for any other
agent vj , there exits a directed path from vi0 to vj .
By Perron-Frobenius theorem [28] (for more detail and
proof, see [29]), we have
Lemma 1: If L is irreducible, then rank(L) = m − 1,
zero is an algebraically simple eigenvalue of L and there is
aPpositive vector ξ ⊤ = [ξ1 , · · · , ξm ] such that ξ ⊤ L = 0 and
m
i=1 ξi = 1.
Let Ξ = diag[ξ1 , · · · , ξm ], by the results first given in [28],
we have
Lemma 2: If L is irreducible, then ΞL + L⊤ Ξ is a symmetric matrix with all row sums equal to zeros and has zero
eigenvalue with algebraic dimension one.
Here we define some matrices, which will be used later. Let
R = [Rij ]m
i,j=1 , where
1
(ΞL + L⊤ Ξ)
2
Obviously, R is positive semi-definite. Denote the eigenvalue
of R by 0 = λ1 < λ2 ≤ · · · ≤ λm , counting the multiplicities.
R=

3

We also denote

=

U = Ξ − ξξ ⊤

i=1

It can also be seen that U has a simple zero eigenvalue and
its eigenvalues (counting the multiplicities) can be arranged as
0 = µ1 < µ2 ≤ · · · ≤ µm . We also denote the eigenvalues of
LT L by 0 = γ1 < γ2 ≤ · · · ≤ γm = ρ(L⊤ L). Then, for all
x ∈ Rm satisfying x⊥1, we have

=
=

Therefore, we have
λ2
UU
µ2m

(3)

γ2
UU
µ2m

(4)

(5)

Pick weight function µ(t) > 0 satisfying µ̇(t)
µ(t) ≤ β.
III. P ULL - BASED EVENT- TRIGGERED PRINCIPLES
In this section, we consider event-triggered control for
multi-agent systems with directed and weighted topology.
Firstly, we consider the case of irreducible L.
Denote
q(t) = [q1 (t), · · · , qm (t)]⊤ , where qi (t) =
Pm
− j=1 Lij xj (t) and f (t) = [f1 (t), · · · , fm (t)]⊤ , where
fi (t) = qi (tik ) − qi (t), t ∈ [tik , tik+1 ), k = 1, 2, ...
To depict the trigger event, consider the following candidate
Lyapunov function (see [28]):
m

1
1X
ξi (xi (t) − x̄(t))2 = x⊤ (t)U x(t)
2 i=1
2
Pm
where x̄(t) = i=1 ξi xi (t).
By the definition, we have
m
X
i=1

ξi (xi (t) − x̄(t)) = 0

ξi (xi (t) − x̄(t)) {fi (t) + qi (t)}
ξi (xi (t) − x̄(t))[fi (t) −

m X
m
X

ξi Lij xj (t) = 0

i=1

The derivative of V (t) along (2) is
m
X
d
˙
ξi (xi (t) − x̄(t))(ẋi (t) − x̄(t))
V (t) =
dt
i=1

=

m
X
i=1

=−

ξi (xi (t) − x̄(t))ẋi (t)

m
X
i=1

ξi (xi (t) − x̄(t))

m
X
j=1

Lij xj (tik )

xi (t)ξi Lij xj (t) +

Lij xj (t)]

j=1
m
X
i=1

i=1 j=1
⊤

ξi (xi (t) − x̄(t))fi (t)

(6)

d
V (t)
dt

aµ2m
λ2
1
)
x⊤ (t)L⊤ Lx(t) + f ⊤ (t)f (t)
⊤
2λ2 ρ(L L)
2a
aµ2m
λ2
1
= − (1 −
)
q ⊤ (t)q(t) + f ⊤ (t)f (t)
2λ2 ρ(L⊤ L)
2a
m
X
aµ2m
λ2
1
[−(1 −
)
=
q 2 (t) + (qi (tik ) − qi (t))2 ]
⊤ L) i
2λ
ρ(L
2a
2
i=1
(10)
≤ − (1 −

and
d[µ(t)V (t)]
= µ(t)V̇ (t) + µ̇(t)V (t)
dt


m
X
λ2
γ2 µ̇(t) 2
aµ2
q (t)
µ(t)
− (1 − m )
+
≤
2λ2 ρ(L⊤ L) µm µ(t) i
i=1

1
i
2
+ (qi (tk ) − qi (t))
(11)
2a
Therefore, we have
Theorem 1: Suppose that G is strongly connected. µ̇(t)
µ(t) ≤
2
β(t). For i = 1, · · · , m,, set 0 < a < 2λ
,
and
µ2
m

(7)

b(t) = (1 −

and due to ξ ⊤ L = 0, we have
m
X

m
X

By (5), we have

and

V (t) =

ξi (xi (t) − x̄(t))qi (tik )

= − x (t)Rx(t) + x⊤ (t)U f (t)
a
1
≤ − x⊤ (t)Rx(t) + x⊤ (t)U U x(t) + f ⊤ (t)f (t)
2
2a
1 ⊤
aµ2m ⊤
)x (t)Rx(t) + f (t)f (t)
≤ − (1 −
(9)
2λ2
2a

x⊤ U U x ≤ µ2m x⊤ x

λm ⊤
λ2
L L≥R≥
L⊤ L
γ2
ρ(L⊤ L)

i=1
m
X

=−

and

LT L ≥

m
X

i=1

λ2 x⊤ x ≤ x⊤ Rx

R≥

m
X

(8)

tik+1 = maxi
τ ≥tk

aµ2m

λ2
γ2 β(t)
)
>0
−
2λ2 ρ(L⊤ L)
µm


τ : qi (tik ) − qi (t)
p
≤ 2ab(t) qi (t) , ∀t ∈ [tik , τ ]

Then, system (2) reaches a consensus


m
X
ξj xj (t) = O µ−1/2 (t)
xi (t) −



(12)

(13)

j=1

In addition, for all i ∈ I, we have and


−1/2
ẋi (t) = O µ
(t)

(14)

4

Proof: Combining inequalities (10), (15) and (5), we have
d[µ(t)V (t)]
≤0
dt

In fact, suppose that there is no trigger event when t > T .
Then, we have
ẋi (t) =

for all t ≥ 0. It means

j=1

V (t) ≤ µ(0)µ−1 (t)

j=1

and
ẋi (t) = −

j=1

xi (t) − xi (T ) = (t − T )

This completes the proof.
As special cases, we have
Corollary 1: Suppose that G is strongly connected. µ(t) =
2
eβt . For i = 1, · · · , m,, set 0 < a < 2λ
µ2 , and
m

tik+1 = max
τ ≥tik

aµ2m
λ2
γ2 β
)
>0
−
2λ2 ρ(L⊤ L)
µm



τ : qi (tik ) − qi (t)
≤

√

2ab qi (t) ,

∀t ∈ [tik , τ ]

Then, system (2) reaches a consensus


m
X
−βt/2
ξj xj (t) = O e
xi (t) −



(15)

(16)

j=1

m
X


|qi (tjk )|
τ:
≤ qi (t)
1+c
≤

|qi (tjk )|
, ∀t ∈ [tik , τ ]
1−c



(19)

for some sufficient small constant c. Then, system (2) reaches
a consensus.
Theorem 1 shows such a constant c does exist.
Remark 1: To utilize event-triggering algorithm, two issues
should be addressed. Firstly, for any initial condition, at any
time t ≥ 0, under the condition and the event-triggered
principle in Theorem 1, there exists at least one agent vj1 ,
of which the next inter-event time is strictly positive before
consensus is reached.

Lij xj (Tkii (T ) ).

j=1

1

m
X

Li2 j xj (Tki2i (T ) )
2

j=1

xi1 (T ) = xi2 (T )
which implies xi1 (t) = xi2 (t) for all t ≥ T and i1 , i2 =
1, · · · , m. It means that in case there is no triggering time for
t > T , the consensus has reached at time T .
Secondly, it should be addressed that in any finite interval
[t1 , t2 , there are only finite triggers. It would be discussed in
the following algorithms.
In the following, we propose another event-triggering setting.
Denote δxi (t) = xi (t) − x̄(t), and rewrite
m
m
X
X
d
Lij xj (t)]
ξi (xi (t) − x̄(t))[fi (t) −
V (t) =
dt
j=1
i=1

(17)

Corollary 2: Suppose that G is strongly connected. Set

i
tk+1 = max τ : qi (tjk ) − qi (t)
τ ≥tik

i
≤ c qi (t) , ∀t ∈ [tk , τ ]
(18)

m
X

and

=−

ẋi (t) = O(e−βt/2 )

tik+1 = max
τ ≥tik

Li1 j xj (Tki1i (T ) ) =

j=1

In addition, for all i ∈ I, we have

or

(20)

By Theorem 1, we have xi1 (t) − xi2 (t) → 0. Therefore, for
all i1 , i2 = 1, · · · , m, we have





−1/2
i
i
(t)
Lij xj (tki (t) ) − x̄(tki (t) ) = O µ

b = (1 −

Lij xj (Tkii (T ) ), t > T, i = 1, · · · , m

which implies

This implies that system (2) reaches consensus and for all
i = 1, · · · , m,


m
X
ξj xj (t) = O µ−1/2 (t)
xi (t) −
m
X

m
X

≤(−

m X
m
X
i=1 j=1

δxi (t)ξi Lij δxj (t) +

m
X

ξi δxi (t)fi (t)

i=1

m
m
λ2
1 X
a X
ξi (δxi (t))2 +
ξi (fi (t))2
+ )
max{ξi } 2 i=1
2a i=1
(21)

and
d[µ(t)V (t)]
dt


m
µ(t) X
a µ̇(t)
λ2
µ(t)V (t) +
ξi (fi (t))2
+ +
≤ −
max{ξi } 2 µ(t)
2a i=1
(22)
Firstly, we give a simple lemma.
Lemma 3: Suppose a function V1 (t) with V1 (0) > 0 and
satisfies
V̇1 (t) ≤ −c1 V1 (t) + c2
for some constants c1 > 0 and c2 > 0. Then, V1 (t) is bounded.
In fact, if V1 (t) > c2 /c1 , then V̇1 (t) < 0.
Theorem 2: Suppose that G is strongly connected, function
µ(t) > 0 satisfies µ̇(t) ≤ βµ(t) for some β > 0 and
−

λ2
a
+ +β <0
max{ξi } 2

5

for some small numbers a and β. For agent vi , if trigger Then, system (2) reaches consensus
times ti1 = 0, · · · , tik are known, then use the following trigger
e−βt/2
strategy to find tik+1 :
(28)
|xi (t) − x̄(t)| ≤ q
λ2
a
n
o
−
−
β)
2aξi ( max{ξ
2
i}
tik+1 = max τ ≥ tik : |qi (tik ) − qi (t)|2 ≤ µ−1 (t), ∀t ∈ [tik , τ ]
(23) and the Zeno behaviour could be excluded; In addition,
ẋj (t) = O(e−βt/2 )

Then, system (2) reaches consensus
|xi (t) −

m
X

µ−1/2 (t)
ξj xj (t)| ≤ q
λ2
2aξi ( max{ξ
− a2 − β)
j=1
i}

(24)

In addition, for all i ∈ I, we have

ẋi (t) = O(µ−1/2 (t))

(25)

and the Zeno behaviour could be excluded.
Proof: By previous derivations, it is clear that there are
two constants c1 > 0 and c2 > 0 such that


d{µ(t)V (t)}
a
1
λ2
≤−
− − β µ(t)V (t) +
dt
max{ξi } 2
2a

By Lemma 3, µ(t)V (t) are bounded. Therefore, for sufficient
large t, we have
µ(t)V (t) ≤
and

1
λ2
− a2 − β)
2a( max{ξ
i}

IV. D ISTRIBUTED SELF - TRIGGERED PRINCIPLES

µ−1 (t)
V (t) ≤
λ2
− a2 − β)
2a( max{ξ
i}
µ−1/2 (t)
|xi (t) − x̄(t)| ≤ q
λ2
− a2 − β)
2aξi ( max{ξ
i}

(26)

In addition, for all i ∈ I and t ∈ [tki , tki +1 ], we have


m
X
i
i
Lij xj (tki ) − x̄(tki ) |
|ẋi (t)| =|
j=1

µ−1/2 (tki )

≤2Lii q
λ2
− a2 − β)
2aξi ( max{ξ
i}

Furthermore, in any finite length interval [0, T ], ||q̇i (t)||2 ≤
M , and µ(t) is bounded. Thus, M (tik+1 − tik )2 ≥ |qi (tik+1 ) −
qi (tik )|2 = µ−1 (tik+1 ) is lower bounded. Then,
µ−1 (tik+1 )
µ−1 (T )
≥
M
M
Therefore, in any finite length interval [0, T ], there are only
finite triggers. It means that Zeno behavior is avoided.
Theorem 3: Suppose that G is strongly connected, and
(tik+1 − tik )2 ≥

−

a
λ2
+ +β <0
max{ξi } 2

Remark 2: (i) In Theorem 2, in order to determine the
trigger times, each agent only needs its in-neighbours’ state
information, especially do not need any a priori knowledge of
any global parameter. (ii) By a little more detail analysis, we
can show that there exists a constant c such that for each agent
vi , tik+1 − tik ≥ c > 0. We omit detail proof here.
Remark 3: By picking different function µ(t), we can obtain different convergence rate. It can be seen that if µ(t)
increases fast, then the interval tik+1 − tik can be larger, which
means less triggers are needed. Instead, if µ(t) increases
slowly, then the interval tik+1 − tik should be smaller, which
means more triggers are needed.
Remark 4: The event-triggered principle used in Theorem
2 may be costly since each agent has to continuously send its
state information to its out-neighbours. In the next section, we
will give an algorithm to avoid this.

for some small numbers a and β. For agent vi , if trigger
times ti1 = 0, · · · , tik are known, then use the following trigger
strategy to find tik+1 :
n
o
tik+1 = max τ ≥ tik : |qi (tik ) − qi (t)|2 ≤ e−βt , ∀t ∈ [tik , τ ]
(27)

In this section, we extend the pull-based event-triggered
principle discussed in Section III to self-triggered case in
order to avoid continuous communication between agents.
Self-triggered approach means that one can predict next triggering time tik based on the information at previous triggering
time tik .
Recall again the model
xi (tik+1 ) = xi (tik ) + (tik+1 − tik )

m
X

aij xj (tjk )

j=1

In centralized control, the bound for (tik+1 − tik ) = (tk+1 − tk )
to reach consensus was given in that paper [15] when the
coupling graph is indirected (or in [16] for direct graph), too.
It means that the idea of self-triggering has been considered
in these two papers.
For agent vi , given ti1 = 0, · · · , tik , its state at t ∈ [tik , tik+1 ]
(tik+1 to be determined) can be written as:
xi (t) = xi (tik ) + (t − tik )qi (tik ), t ∈ [tik , tik+1 ]

(29)

Since each agent vp ∈ Niin sends trigger information to agent
vi whenever agent vp triggers, then at any given time point r,
agent vi can predict agent vp ’s state at time t ≥ r as
xp (t) = xp (tpkp (r) ) + (t − tpkp (r) )qp (tpkp (r) )

(30)

until agent vp ’ next triggering after s.
Then, from Theorem 3, we have the following result
Theorem 4: Suppose that G has spanning trees and L is
written in the form of (32). For agent vi , pick φi > 0, αi >
0. If trigger times ti1 = 0, · · · , tik are known, then use the
following trigger strategy to find tik+1 :

6

1) At time s = tik , substituting (29) and (30) into (40),
Property 1: Under the setup above, Qk = 21 [Ξk Lk,k +
and solve the following maximizing problem to find out (Ξk Lk,k )⊤ ] = Rk + Ξk Dk is positive definite and Ξk ≤
i
ρ(Ξk )
τk+1
:
Qk for all k < K.
ρ2 (Qk )
n
o And let U K = ΞK − ξ K (ξ K )⊤ and in order to facilitate the
i
τk+1
= max τ ≥ s : |qi (tik ) − qi (t)| ≤ e−βt , ∀t ∈ [s, τ ] presentation, also denote U k = Ξk , k = 1, · · · , K − 1.
(31)
Now we are going to determine the triggering times for the
system (2) to reach consensus. Firstly, applying Theorem 1 to
2) In case that some in-neighbours of agent vi triggers the K-th SCC, we can conclude that the K-th SCC can reach
i
at time t0 ∈ (s, τk+1
), i.e., agent vi received the a consensus with the agreement value ν(t) = PnK ξ K xK (t)
p=1 p p
renewed information form some of its in-neighbours, and lim
t→∞ ν̇(t) = 0 exponentially.
then updating s = t0 and go to step (1);
Then, inductively, consider the K −1-th SCC. We will prove
3) In case that any of vi ’s in-neighbours does not trigger that lim
K−1
(t) − ν(t)| = 0, for all p = 1, · · · , nK−1 .
t→∞ |xp
i
i
during (s, τk+1
), then vi triggers at time tik+1 = τk+1
.
Construct
a
candidate
Lyapunov function as follows
The agent vi renews its state at t = tik+1 and sends
1
the renewed information, including tik+1 , xi (tik+1 ) and
VK−1 (t) = (xK−1 (t) − ν(t)1)⊤ ΞK−1 (xK−1 (t) − ν(t)1)
i
2
qi (tk+1 ), to all its out-neighbours immediately.
(33)
then, system (2) reaches consensus exponentially and the Zeno
Differentiate VK−1 (t) along (2), we have
behaviour could be excluded.
d
Remark 5: Obviously, Theorem 4 can be regarded as an
VK−1 (t)
dt
algorithm of Theorem 3, by which the continuous communin
o
cations between different states can be avoided.
=(xK−1 (t) − ν(t)1)⊤ ΞK−1 f K−1 (t) + q K−1 (t) − ν̇(t)1
n
Secondly, we consider the case L is reducible. The folK−1
(t) − ν(t)1)⊤ ΞK−1 f K−1 (t) − ν̇(t)1
lowing mathematical methods are inspired by [31]. By proper =(x
o
permutation, we rewrite L as the following Perron-Frobenius
K−1,K−1 K−1
K−1,K K
−
L
(x
(t)
−
ν(t)1)
−
L
(x
(t)
−
ν(t)1)
form:

 1,1
=(xK−1 (t) − ν(t)1)⊤ ΞK−1 f K−1 (t)
L
L1,2 · · · L1,K
 0
− [xK−1 (t) − ν(t)1]⊤ ΞK−1 LK−1,K−1 [xK−1 (t) − ν(t)1]
L2,2 · · · L2,K 



L= .
(32)

..
.
..
− (xK−1 (t) − ν(t)1)⊤ ΞK−1 LK−1,K (xK (t) − ν(t)1)

 ..
. ..
.
0
0
· · · LK,K
− (xK−1 (t) − ν(t)1)⊤ ΞK−1 {ν̇(t)1}

where Lk,k is with dimension nk and associated with the k-th
strongly connected component (SCC) of G, denoted by SCCk ,
T
T
k = 1, · · · , K. Accordingly, define x = [x1 , · · · , xK ]T ,
where xk = [xk1 , · · · , xknk ]⊤ .
For agent vi ∈ SCCP
k , i.e., i = Mk−1 + 1, · · · , Mk ,
k
where M0 = 0, Mk = i=1
Pni , denote the combinational
k
state measurement qi (t) = − m
j=Mk−1 +1 Li+Mk−1 ,j xj (t) =
Pm
− j=1 Li+Mk−1 ,j xj (t) = qi+Mk−1 (t). And denote the comi+M
binational measurement error by fik (t) = qik (tl k−1 )− qik (t)
i+M
i+M
i+M
and uki (t) = qik (tl k−1 ), t ∈ [tl k−1 , tl+1 k−1 ).
k,k
If G has spanning trees, then each L is irreducible or has
one dimension and for each k < K, Lk,q 6= 0 for at least one
nk
q > k. Define an auxiliary matrix L̃k,k = [L̃k,k
ij ]i,j=1 as
(
Lk,k
i 6= j
k,k
ij
L̃ij =
Pnk
k,k
− p=1,p6=i Lip i = j

Then, let Dk = Lk,k − L̃k,k = diag[D1k , · · · , Dnk k ], which is
a diagonal semi-positive definite matrix and has at least one
diagonal positive (nonzero).
⊤
Let ξ k be the positive left eigenvector of the irreducible
L̃k,k corresponding to the eigenvalue zero and has the sum
of components equaling to 1. Denote Ξk = diag[ξ k ]. By the
structure, it can be seen that Rk = 12 [Ξk L̃k,k + (Ξk L̃k,k )⊤ ]
has zero row sums and has zero eigenvalue with algebraic
dimension one. Then, we have

=W0K−1 (t) − W1K−1 (t) − W2K−1 (t) − W3K−1 (t)

(34)

where
W0K−1 (t) = (xK−1 (t) − ν(t)1)⊤ ΞK−1 f K−1 (t)
nK−1
X
1
ξ K−1 [fiK−1 ]2
≤ aK−1 VK−1 (t) +
2aK−1 i=1 i

(35)

with any aK−1 > 0,
W1K−1 (t)

= [xK−1 (t) − ν(t)1]⊤ ΞK−1 LK−1,K−1 [xK−1 (t) − ν(t)1]

= [xK−1 (t) − ν(t)1]⊤ QK−1,K−1 [xK−1 (t) − ν(t)1]

(36)

W2K−1 (t) = (xK−1 (t) − ν(t)1)⊤ ΞK−1 LK−1,K (xK (t) − ν(t)1)
W3K−1 (t) = (xK−1 (t) − ν(t)1)⊤ ΞK−1 (ν̇(t)1)
By Cauchy inequality, for any υ2K−1 > 0, υ3K−1 > 0, we
have
−W2K−1 (t) ≤ υ2K−1 VK−1 (t) + F2K−1 (t)

−W3K−1 (t) ≤ υ3K−1 VK−1 (t) + F3K−1 (t)

(37)

where
F2K−1 (t) =
F3K−1 (t) =

1

nK−1

LK−1,K
[xK
p (t) − ν(t)]
i,p

ξiK−1

X

ξiK−1 [ν̇(t)]2 =

4υ2K−1 i=1
1

(n
K
X

X

nK−1

4υ2K−1 i=1

p=1

1
2υ3K−1

[ν̇(t)]2

)2

7

According to the discussion of SCCK and Theorem ??,
for all p = 1, · · · , nK , we have limt→∞ xK
p (t) − ν(t) =
0, limt→∞ ν̇(t) = 0 exponentially. Thus
lim F2K−1 (t) = 0, lim F3K−1 (t) = 0

t→∞

(38)

t→∞

exponentially.
Thus, (34) can be rewritten as follows
nK−1
X
d
1
ξ K−1 [fiK−1 ]2
VK−1 (t) ≤ aK−1 VK−1 (t) +
dt
2aK−1 i=1 i

− W1K−1 (t) − W2K−1 (t) − W3K−1 (t)


aK−1 ρ(ΞK−1 )
W1K−1 (t) − W2K−1 (t)
≤− 1−
2ρ2 (QK−1 )
nK−1
X
1
+
ξ K−1 [fiK−1 ]2 − W3K−1 (t)
2aK−1 i=1 i

(39)

Thus, we have
Theorem 5: Suppose that G has spanning trees and L is
written in the form of (32). For agent vi , if trigger times ti1 =
0, · · · , tik are known, then use the following trigger strategy
to find tik+1 :
n
o
tik+1 = max τ ≥ tik : |qi (tik ) − qi (t)| ≤ e−βt , ∀t ∈ [tik , τ ]
(40)
system (2) reaches consensus exponentially and the Zeno
behaviour could be excluded.
Proof: If vi ∈ K-th SCC, the event-triggered rule (40) is
the same as (27) in Theorem 3, since L is written in the form of
(32). By Theorem 3, we can conclude that under the updating
j+M
rule of {tl K−1 }for all j = 1, · · · , nK and limt→∞ ν̇(t) =
0, the subsystem restricted in SCCK reaches a consensus.
Additionally, limt→∞ |xK
i (t)−ν(t)| = 0 for all i = 1, · · · , nK
and limt→∞ ν̇(t) = 0 as well.
In the following, we are to prove that the state of the agent
vp+MK−2 ∈ SCCK−1 converges to ν(t). The remaining can
be proved similarly by induction.
From (39) and the inequality (40), we have

d
aK−1 ρ(ΞK−1 ) ρ2 (QK−1 )
VK−1 (t) ≤ − [1 −
VK−1 (t)
dt
2ρ2 (QK−1 )
ρ(U K−1 )
+ (υ2K−1 + υ3K−1 )VK−1 (t) + W4K−1 (t)

From (38), we have limt→∞ W4K−1 (t) = 0 exponentially. Thus, we have limt→∞ VK−1 (t) = 0 exponentially.This implies that system (2) reaches a consensus and
limt→∞ |xK−1
(t) − ν(t)| = 0 exponentially for all p =
p
1, · · · , nK−1 .
Similar to the proof in Theorem 3, we can prove that the
Zeno behaviour can be excluded for agent vi ∈ K − 1-th SCC.
Then, we can complete the proof by induction to SCCk for
k < K − 1.
V. E XAMPLES
In this section, one numerical example is given to demonstrate the effectiveness of the presented results.
Consider a network of seven agents with a directed reducible
Laplacian matrix


−12
0
5
2
5
0
0

3 −8
3
0
0
0
2 



0
4
−12
3
0
5
0 


0
0
6 −11
1
4
0 
L=



0
0
0
0 −7
2
5 



0
0
0
0
5 −6
1 
0
0
0
0
0
8 −8

with a spanning tree described by Figure 1. The seven agents
can be divided into two strongly connected components,
i.e. the first four agents form a strongly connected component and the rest form anther. The initial value of each
agent is also randomly selected within the interval [−5, 5]
in our simulation. Figure 2 (a) shows the evolution of the
Lyapunov function V (t) = V1 (t) + V2 (t) (see (33)), and
Figure 2 (b) illustrates the trigger times of each agents under
the self-triggered principles provided in Theorem 4 with
φi = 20 and αi = 1.5, i = 1, · · · , 7, and initial value
[2.192, −3.699, −2.982, 4.726, 3.575, 4.074, −3.424]⊤. It can
be seen that under the self-triggering principle in Theorem 4,
V (t) approaches 0 exponentially and the inter-event times of
each agent are strictly bigger than some positive constants.

3

1

2
4

5
2

3

6
4

3
3

5

4

1

where

5

2

6

W4K−1 (t) = F2K−1 (t) + F3K−1 (t) +

1

2

nK−1

X

2aK−1 j=1

8
1

5

ξjK−1 δj2 (t)

5

7
5

K−1

)
2 (Q
Picking aK−1 = ρρ(Ξ
and sufficiently small υ2K−1 and
K−1 )
υ3K−1 , there exists some εK−1 > 0 such that

d
VK−1 (t) ≤ −εK−1 VK−1 (t) + W4K−1 (t)
dt
Thus
VK−1 (t) ≤ e

−εK−1 t



Z t
K−1
εK−1 s
VK−1 (0) +
e
W4
(s)ds
0

Fig. 1.

The communication graph.

VI. C ONCLUSIONS
In this paper, we present distributed event-triggered and
self-triggered principles in for multi-agent systems with general directed topologies. We derive pull-based event-triggered

8

(a) The evolution of the Lyapunov function
15
V(t) in Theorem 3
10
5
0
0

agent 7
agent 6
agent 5
agent 4
agent 3
agent 2
agent 1
0

0.5

1

1

1.5
2
t
(b) Triggers in Theorem 3

2

3

4

5

2.5

6

7

8

t

Fig. 2. The evolution of the Lyapunov function and the trigger times of each
agents..

principles: in case the graph is reducible with a spanning
tree, the triggering time of each agent given by the inequality
(40) only depends on the states of each agent’s in-neighbors.
It is shown that with those principles, consensus can be
reached exponentially, and Zeno behavior can be excluded.
The results then are extended to discontinuous monitoring,
where each agent computes its next triggering time in advance
without having to observe the systems state continuously. The
effectiveness of the theoretical results are verified by one
numerical example.
R EFERENCES
[1] F. C HEN , Z. C HEN , L. X IANG , ET AL ., Reaching a consensus via pinning
control, Automatica, vol. 45, no. 5, pp. 1215-1220, 2009.
[2] R. O. S ABER , AND R. M. M URRAY, Consensus Problems in Networks of
Agents With Switching Topology and Time-Delays, IEEE Trans. Autom.
Control, vol. 49, no. 9, pp. 1520–1533, Sep. 2004.
[3] L. C AO , Y. F. Z HENG , AND Q. Z HOU, A necessary and sufficient
condition for consensus of continuous-time agents over undirected timevarying networks, IEEE Trans. Autom. Control, vol. 56, no. 8, pp. 19151920, Aug. 2011.
[4] B. L IU , W. L. L U , AND T. P. C HEN, Consensus in networks of multiagents with switching topologies modeled as adapted stochastic processes,
SIAM J. Control optim., vol. 49, no. 1, pp. 227-253, 2011.
[5] P. TABUADA, Event-triggered real-time scheduling of stabilizing control
tasks, IEEE Trans. Autom. Control, vol. 52, no. 9, pp. 1680-1685, Sep.
2007.
[6] W.P.M.H. H EEMELS , J.H. S ANDEE , AND P.P.J. VAN D EN B OSCH,
Analysis of event-driven controllers for linear systems, Int. J. Control,
vol. 81, no. 4, pp. 571-590, 2007.
[7] M. J. M ANUEL , AND P. TABUADA, Decentralized event-triggered control
over wireless sensor/actuator networks, IEEE Trans. Autom. Control, vol.
56, no. 10, pp. 2456-2461, Oct. 2011.
[8] X.WANG , AND M. D. L EMMON, Event-triggering distributed networked
control systems, IEEE Trans. Autom. Control, vol. 56, no. 3, pp. 586-601,
Mar. 2011.
[9] C. P ERSIS , R. S AILER , AND F. W IRTH, Parsimonious event-triggered
distributed control: A zeno free approach, Automatica, vol. 49, no. 7, pp.
2116-124, 2013.
[10] A. A NTA , AND P. TABUADA, Self-triggered stabilization of homogeneous control systems, in Proc. Amer. Control Conf., 2008, pp. 41294134.
[11] M. M AZO , AND P. TABUADA, On event-triggered and self-triggered
control over sensor/actuator networks, in Proc. 47th IEEE Conf. Decision
Control, 2008, pp. 435-440.

[12] X.WANG AND M. D. L EMMON, Self-triggered feedback control systems
with finite-gain L2 stability, IEEE Trans. Autom. Control, vol. 45, no. 3,
pp. 452-467, Mar. 2009.
[13] M. J. M ANUEL , A. A NTA , AND P. TABUADA, An ISS self-triggered
implementation of linear controllers, Automatica, vol. 46, no. 8, pp. 13101314, 2010.
[14] A. A NTA AND P. TABUADA, To sample or not to sample: self-triggered
control for nonlinear systems, IEEE Trans. Autom. Control, vol. 55, no.
9, pp. 2030-2042, Sep. 2010.
[15] W.L. L U , AND T.P. C HEN, Synchronization Analysis of Linearly Coupled Networks of Discrete Time Systems, Physica D, VOL. 198, PP. 148168, 2004.
[16] W.L. L U , AND T.P. C HEN, Global Synchronization of Discrete-Time
Dynamical Network With a Directed Graph, IEEE Transactions on
Circuits and Systems-II: Express Briefs, vol. 54, no. 2, pp. 136-140, 2007.
[17] D. V. D IMAROGONAS , E. F RAZZOLI , AND K. H. J OHANSSON, Distributed event-triggered control for multi-agent systems, IEEE Trans.
Autom. Control, vol. 57, no. 5, pp. 1291-1297, May 2012.
[18] Z. L IU , Z. C HEN , AND Z. Y UAN, Event-triggered average-consensus of
multi-agent systems with weighted and direct topology, Journal of Systems
Science and Complexity, vol. 25, no. 5, pp. 845-855, 2012.
[19] G. S. S EYBOTH , D. V. D IMAROGONAS , AND K. H. J OHANSSON,
Event-based broadcasting for multi-agent average consensus, Automatica, vol. 49, pp. 245-252, 2013.
[20] Y. FAN , G. F ENG , Y. WANG , AND C. S ONG, Distributed event-triggered
control of multi-agent systems with combinational measurements, Automatica, vol. 49, pp. 671-675, 2013.
[21] E. G ARCIA , ET AL ., Decentralised event-triggered cooperative control
with limited communication, International Journal of Control, vol. 86, no.
9, pp. 1479-1488, 2013.
[22] X.Y. M ENG , AND T.W. C HEN, Event based agreement protocols for
multi-agent networks, Automatica, vol. 49, pp. 2125-2132, 2013.
[23] W. Z HU , Z.P. J IANG , AND G. F ENG, Event-based consensus of multiagent systems with general linear models, Automatica, vol. 50, pp. 552558, 2014.
[24] W.L. L U , AND T.P. C HEN, New Approach to Synchronization Analysis
of Linearly Coupled Ordinary Differential Systems, Physica D, 213, 214230 2006.
[25] C. N OWZARI , AND G. C ORT ÉS , Zeno-free, distributed event-triggered
communication and control for multi-agent average consensus, In Proc.
Amer. Control Conf., pp. 2148-2153, 2014.
[26] R. D IESTEL, Graph theory, Graduate texts in mathematics 173, New
York: Springer-Verlag Heidelberg, 2005.
[27] R. A. H ORN , AND C. R. J OHNSON, Matrix Analysis, Cambridge, U.K.:
Cambridge Univ. Press, 1987.
[28] W.L. L U , AND T.P. C HEN, New Approach to Synchronization Analysis
of Linearly Coupled Ordinary Differential Systems, Physica D, vol. 213,
pp. 214-230, 2006
[29] W.L. L U , AND T.P. C HEN, A New Approach to Synchronization Analysis
of Linearly Coupled Map Lattices, Chinese Annals of Mathematics, vol.
28B, no. 2, pp. 149-160, 2007.
[30] K.H. J OHANSSON , M. E GERSTEDT, J. LYGEROS , AND S.S. S ASTRY,
On the regularization of zeno hybrid automata, Systems and Control
Letters, vol. 38, pp. 141-150, 1999.
[31] T.P. C HEN , X.W. L IU , AND W.L. L U, Pinning complex networks by a
single controller, IEEE Trans. Circuits and Systems, vol. 54, no. 6, pp.
1317-1326, Jun. 2007.

x1

2

x2
x3

state value

1

x4

0

x5
x6

−1

x7
−2
−3
−4
0

0.5

1

1.5
t

2

2.5

