1

A Jamming-resilient Algorithm for Self-triggered
Network Coordination

arXiv:1603.02563v1 [] 8 Mar 2016

Danial Senejohnny, Pietro Tesi, and Claudio De Persis

Abstract—The issue of cyber-security has become ever more
prevalent in the analysis and design of cyber-physical systems.
In this paper, we investigate self-triggered consensus networks
in the presence of communication failures caused by Denialof-Service (DoS) attacks. A general framework is considered
in which the network links can fail independent of each other.
By introducing a notion of Persistency-of-Communication (PoC),
we provide an explicit characterization of DoS frequency and
duration under which consensus can be preserved by suitably
designing time-varying control and communication policies. An
explicit characterization of the effects of DoS on the consensus
time is also provided. The considered notion of PoC is compared
with classic average connectivity conditions that are found in
pure continuous-time consensus networks. Finally, examples are
given to substantiate the analysis.
Index Terms—Consensus networks; Self-triggered control;
Denial-of-Service.

I. I NTRODUCTION

R

Ecent years have witnessed a growing interest towards
Cyber-Physical systems (CPSs), namely systems that
exhibit a tight conjoining of communication, computational
and physical units. The fact that breaches in the cyber-space
can have consequences in the physical domain has triggered
considerable attention towards the issue of cyber-physical
security [1], [2]. In CPSs, attacks to the communication links
can be classified as either deception attacks or Denial-ofService (DoS) attacks. The former affect the trustworthiness of
data by manipulating the packets transmitted over the network;
see [3]-[4] and the references therein. DoS attacks are instead
primarily intended to affect the timeliness of the information
exchange, i.e., to cause packet losses. This paper is concerned
with DoS attacks, and, in particular, with jamming attacks
[5], [6], although in this paper we shall use these two terms
interchangeably.
In the literature, the issues of securing robustness of CPSs
against DoS has been widely investigated only for centralized
architectures [7]-[14]. On the other hand, very little is known
about DoS for distributed coordination problems. In this paper,
we investigate the issue of DoS with respect to consensus-like
networks. Specifically, inspired by [15], we consider a selftriggered consensus network, in which communication and
control actions are planned ahead in time, depending on the
information currently available at each agent. The attacker
objective is to prevent consensus by denying communication
Danial Senejohnny, P. Tesi, and C. De Persis are with ENTEG and
Jan C. Willems Center for Systems and Control, University of Groningen, 9747 AG Groningen, The Netherlands e-mail: {d.senejohnny, p.tesi,
c.de.persis}@rug.nl.

among the network agents. Consensus is a prototypical problem in distributed settings with a huge range of applications,
spanning from formation and cooperative robotics to surveillance and distributed computing; see for instance [15]-[16].
On the other hand, self-triggered coordination turns out to be
of major interest when consensus has to be achieved in spite
of possibly severe communication constraints. In this respect,
a remarkable feature of self-triggered coordination lies in the
possibility of ensuring consensus properties in the absence of
any global information on the graph topology and with no
need to synchronize the agents local clocks.
A basic question in the analysis of distributed coordination
in the presence of DoS is concerned with the modeling of DoS
attacks. In [12], [13], a general model is considered that only
constrains DoS attacks in terms of their average frequency and
duration, which makes it possible to capture many different
types of DoS attacks, including trivial, periodic, random and
protocol-aware jamming attacks [5], [6], [17], [18]. Building
on [13], a preliminary analysis of consensus networks in the
presence of DoS is presented in [19] under the simplifying
assumption that the occurrence of DoS cause all the network
links to fail simultaneously. This scenario is representative of
networks operating through a single access point, in the socalled “infrastructure” mode. In this paper, we consider the
more general scenario in which the network communication
links can fail independent of each other, thereby extending the
analysis to “ad-hoc” (peer-to-peer) networks. One contribution
of this paper is an explicit characterization of the frequency
and duration of DoS at the various network links under which
consensus can be preserved by suitably designing time-varying
control and communication policies. Moreover, an explicit
characterization of the effects of DoS on the consensus time
is provided.
Since DoS induces communication failures, the problem of
achieving consensus under DoS can be naturally cast as a
consensus problem for networks with switching topologies.
This approach is certainly not new in the literature. In [20],
for instance, it is shown that consensus can be reached whenever graph connectivity is preserved point-wise in time; [21]
considers a notion of Persistency-of-Excitation (PoE), which
stipulates that graph connectivity should be established over a
period of time, rather than point-wise in time, which is similar
to the joint connectivity assumption in [22]. In CPSs, however,
the situation is different. In CPSs, one needs to deal with the
fact that networked communication is inherently digital, which
means that the rate at which the transmissions are scheduled
cannot be arbitrarily large. Under such circumstances, the
aforementioned tools turn out be ineffective. In order to cope

2

with this situation, we introduce a notion of Persistencyof-Communication (PoC), which naturally extends the PoE
condition to a digital networked setting by requiring graph
(link) connectivity over periods of time that are consistent
with the constraints imposed by the communication medium.
A characterization of DoS frequency and duration under which
consensus properties can be preserved is then obtained by
exploiting the PoC condition.
The remainder of this paper is as follows. In Section II,
we formulate the control problem and provide prototypical
results for self-triggered consensus. In Section III, we describe
the considered class of DoS signals. The main results of
this paper are presented in Section IV. In Section V, we
provide a detailed discussion of the results, and show how
the analysis can be extended so as to account for genuine
(non-malicious) transmission failures. A numerical example
is presented in Section VI. Section VII ends the paper with
concluding remarks.

where for every i ∈ I and j ∈ Ni , the map f ij : Rn → R>0
is defined by

|Dij (t)|


if |Dij (t)| ≥ ε
2(di + dj )
(5)
f ij (x(t)) :=
ε

ij

if
|D
(t)|
<
ε
2(di + dj )
and
Dij (t) = xj (t) − xi (t)

II. S ELF - TRIGGERED CONSENSUS NETWORK

(6)
ij

A. System definition
We consider a consensus network, which is represented
by an undirected graph G = (I, E), where I = {1, . . . , n}
denotes the node set and E ⊆ I × I denotes the edge
set. Specifically, we denote by D and L the incidence and
Laplacian matrix of G, respectively. For each node i ∈ I, we
denote by Ni the set of its neighbors, and by di = |Ni |, i.e.,
the cardinality of Ni . Throughout the paper, we shall refer to
G as the “nominal” network, and we shall assume that G is
connected.
The consensus network of interest employs self-triggered
communication [15], defined via hybrid dynamics, with state
variables (x, u, θ) ∈ Rn × Rd × Rd , where x is the vector
of nodes states, u is the vector of controls, θ is the vector of
clock variables, and
Pn d is the sum of the neighbors of all the
nodes, i.e., d := i=1 di . The control signals are assumed to
belong to T := {−1, 0, +1}. The specific quantizer of choice
is signε : R → T , which is given by
(
sign(z) if |z| ≥ ε
signε (z) :=
(1)
0
otherwise
where ε > 0 is a sensitivity parameter, which can be used at
the design stage for trading-off frequency of the transmissions
vs. accuracy of the consensus region.
The system (x, u, θ) ∈ Rn ×Rd ×Rd satisfies the continuous
evolution

X
i

ẋ
=
uij



j∈Ni
(2)
ij
u̇
=
0



 θ̇ij = −1
where i ∈ I and j ∈ Ni . The system satisfies the differential
equation above for all t except for those values of the time at
which the set
J (θ, t) = {(i, j) ∈ I × I : j ∈ Ni and θij (t− ) = 0}

is non-empty. At these times, in the “nominal” operating mode
(when communication between nodes is always possible), a
discrete transition occurs, which is governed by the following
discrete update:

i −
xi (t) = x(
(t ) ∀i ∈ I





ij

if (i, j) ∈ J (θ, t)

 uij (t) = signε D (t)
ij −
u (t )
otherwise
(4)
(


ij

f
(x(t))
if
(i,
j)
∈
J
(θ,
t)


ij

 θ (t) =
θij (t− )
otherwise

(3)

ij

Notice that for all {i, j} ∈ E we have θ (t) = θ (t) and
uij (t) = −uij (t) for all t ∈ R≥0 . As such, the system
(2)-(4) can be regarded as an edge-based consensus protocol.
Here, the term “self-triggered”, first adopted in the context of
real-time systems [23], expresses the property that the data
exchange between nodes is driven by local clocks, which
avoids the need for a common global clock.
B. Prototypical result for self-triggered consensus
The following result characterizes the limiting behavior of
the system (2)-(4).
Theorem 1: [15] Let x be the solution to (2)-(4). Then, for
every initial condition, x converges in finite time to a point
x∗ ∈ Rn belonging to the set
E = {x ∈ Rn : |xi (t) − xj (t)| < δ

∀ (i, j) ∈ I × I}

(7)

where δ = ε(n − 1).

Theorem 1 will be used as a reference frame for the analysis
of Section IV and V. This theorem is prototypical in the sense
that it serves to illustrate the salient features of the problem
of consensus/coordination in the presence of communication
interruptions. Following [15], the analysis of this paper could
be extended to include important aspects such as quantized
communication, delays and asymptotic consensus (rather than
practical consensus as in (7)). While important, these aspects
do not add much to the present investigation and will be
therefore omitted. We refer the interested reader to [15] for
a discussion on how these aspects can be dealt with.
III. N ETWORK D ENIAL - OF -S ERVICE
We shall refer to Denial-of-Service (DoS, in short) as the
phenomenon by which communication between the network
nodes is interrupted. We shall consider the very general
scenario in which the network communication links can fail
independent of each other. From the perspective of modeling,
this amounts to considering multiple DoS signals, one for each
network communication link.

SENEJOHNNY et al.: A JAMMING-RESILIENT ALGORITHM FOR SELF-TRIGGERED NETWORK COORDINATION

A. DoS characterization
{hij
n }n∈Z≥0

hij
0 ≥

0 denote the sequence of DoS
Let
with
off/on transitions affecting the link {i, j}, namely the sequence
of time instants at which the DoS status on the link {i, j}
exhibits a transition from zero (communication is possible) to
one (communication is interrupted). Then
 ij ij

ij
Hnij := {hij
(8)
n } ∪ hn , hn + τn
represents the n-th DoS time-interval, of a length τnij ∈ R≥0 ,
during which communication on the link {i, j} is not possible.
Given t, τ ∈ R≥0 , with t ≥ τ , let
[
\
Ξij (τ, t) :=
Hnij
[τ, t]
(9)
n∈Z≥0

and
Θij (τ, t) := [τ, t] \ Ξij (τ, t)

(10)

where \ denotes relative complement. In words, for each
interval [τ, t], Ξij (τ, t) and Θij (τ, t) represent the sets of time
instants where communication on the link {i, j} is denied and
allowed, respectively.
The first question to be addressed is that of determining
a suitable modeling framework for DoS. Following [13], we
consider a general model that only constrains DoS attacks in
terms of their average frequency and duration. Let nij (τ, t)
denote the number of DoS off/on transitions on the link {i, j}
occurring on the interval [τ, t].
Assumption 1 (DoS frequency): For each {i, j} ∈ E, there
exist η ij ∈ R≥1 and τfij ∈ R>0 such that
nij (τ, t) ≤ η ij +

t−τ
τfij

(11)

for all t, τ ∈ R≥0 with t ≥ τ .

Assumption 2 (DoS duration): For each {i, j} ∈ E, there
exist κij ∈ R≥0 and τdij ∈ R>1 such that
|Ξij (τ, t)| ≤ κij +

t−τ
τdij

(12)

for all t, τ ∈ R≥0 with t ≥ τ .

In Assumption 1, the term “frequency” stems from the fact
that τfij provides a measure of the “dwell-time” between any
two consecutive DoS intervals on the link {i, j}. The quantity
η ij is needed to render (11) self-consistent when t = τ = hij
n
for some n ∈ Z≥0 , in which case nij (τ, t) = 1. Likewise,
in Assumption 2, the term “duration” is motivated by the fact
that τdij provides a measure of the fraction of time (τdij > 1)
the link {i, j} is under DoS. Like η ij , the constant κij plays
the role of a regularization term. It is needed because during
ij
ij
ij
ij
ij
a DoS interval, one has |Ξ(hij
n , hn + τn )| = τn ≥ τn /τd
ij
ij
since τd > 1, with τnij = τnij /τd if and only if τnij = 0.
Hence, κij serves to make (12) self-consistent. Thanks to the
quantities η ij and κij , DoS frequency and duration are both
average quantities.
Remark 1: Throughout this paper, we will mostly focus on
the case where DoS is caused by malicious attacks. Of course,
DoS might also result from a “genuine” network congestion.
We shall briefly address this case in Section V-C.


3

B. Examples
The considered assumptions only pose limitations on the
frequency of the DoS status and its duration. As such, this
characterization can capture many different scenarios, including trivial, periodic, random and protocol-aware jamming
attacks [5], [6], [17], [18]. For the sake of simplicity, we limit
out discussion to the case of radio frequency (RF) jammers,
although similar considerations can be made with respect to
spoofing-like threats [24].
Consider for instance the case of constant jamming, which
is one of the most common threats that may occur in a wireless
network [5], [25]. By continuously emitting RF signals on the
wireless medium, this type of jamming can lower the Packet
Send Ratio (PSR) for transmitters employing carrier sensing
as medium access policy as well as lower the Packet Delivery
Ratio (PDR) by corrupting packets at the receiver. In general,
the percentage of packet losses caused by this type of jammer
depends on the Jamming-to-Signal Ratio and can be difficult to
quantify as it depends, among many things, on the type of antijamming devices, the possibility to adapt the signal strength
threshold for carrier sensing, and the interference signal power,
which may vary with time. In fact, there are several provisions
that can be taken in order to mitigate DoS attacks, including
spreading techniques, high-pass filtering and encoding [26],
[18]. These provisions decrease the chance that a DoS attack
will be successful, and, as such, limit in practice the frequency
and duration of the time intervals over which communication
is effectively denied. This is nicely captured by the considered
formulation.
As another example, consider the case of reactive jamming
[5], [25]. By exploiting the knowledge of the 802.1i MAC
layer protocols, a jammer may restrict the RF signal to the
packet transmissions. The collision period need not be long
since with many CRC error checks a single bit error can
corrupt an entire frame. Accordingly, jamming takes the form
of a (high-power) burst of noise, whose duration is determined
by the length of the symbols to corrupt [26], [27]. Also
this case can be nicely accounted for via the considered
assumptions.
IV. D O S- RESILIENT CONSENSUS
A. Modified communication protocol
In order to achieve robustness against DoS, the nominal
discrete evolution (4) is modified as follows:


xi (t) = xi (t− ) ∀i ∈ I









signε Dij (t)







uij (t) =
0





 uij (t− )



ij





 f (x(t))



ε

ij


 θ (t) =  2(di + dj )




 ij −


θ (t )

if (i, j) ∈ J (θ, t) ∧ t ∈ Θij (0, t)
if (i, j) ∈ J (θ, t) ∧ t ∈ Ξij (0, t)
otherwise
if (i, j) ∈ J (θ, t) ∧ t ∈ Θij (0, t)
if (i, j) ∈ J (θ, t) ∧ t ∈ Ξij (0, t)
otherwise
(13)
ij

In words, the control action u is reset to zero whenever the
link {i, j} is in DoS status. Notice that this requires that the

4

nodes are able to detect the occurrence of DoS. This is the
case, for instance, with transmitters employing carrier sensing
as medium access policy. Under such circumstances, a DoS
signal in the form of constant jamming (cf. Section III-B)
can be detected. Another example is when transceivers use
TCP acknowledgment and DoS takes the form of reactive
jamming (cf. Section III-B). In addition to u, also the local
clocks are modified upon DoS, yielding a two-mode sampling
logic. In particular, for each {i, j} ∈ E, let {tij
k }k∈Z≥0 denote
the sequence of transmission attempts. Then, each θij satisfies
 ij
ij
ij
if tij

k ∈ Θ (0, t)
 f (x(tk ))
ij
(14)
tij
k+1 = tk + 
ε

otherwise
2(di + dj )

As for i), the following result holds true.
Proposition 1: (Convergence of the solutions) Let x be the
solution to (2) and (13). Then, for every initial condition, there
exists a finite time T∗ such that,for any i ∈ I, it holds that
ui (t) = 0 for all t ≥ T∗ .
Proof. Consider the Lyapunov function
V (x) =

V̇ (x(t)) =

2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

initialization: For all i ∈ I and j ∈ NiP
, set θij (0− ) = 0,
ij −
i −
u (0 ) ∈ {−1, 0, +1}, and u (0 ) = j∈Ni uij (0− );
for all i ∈ I do
for all j ∈ Ni do
while θij (t) > 0 do
P
i applies the control ui (t) = j∈Ni uij (t);
end while
if θij (t− ) = 0 ∧ t ∈ Θij (0, t) then

i updates uij (t) = signε xj (t) − xi (t) ;
i updates θij (t) = f ij (x(t));
else
if θij (t− ) = 0 ∧ t ∈ Ξij (0, t) then
i updates uij (t) = 0;
ε
i updates θij (t) =
;
2(di + dj )
end if
end if
end for
end for

B. Convergence of the solutions and δ-consensus
We are now in position to characterize the overall network
behavior in the presence of DoS. In this respect, the analysis
is subdivided into two main steps: i) we first prove that all the
network nodes eventually stop to update their local controls;
and ii) we then provide conditions on the DoS frequency and
duration such that consensus, in the sense of (7), is preserved.
The latter property is achieved by resorting to a notion of
Persistency-of-Communication, which determines the amount
of DoS (frequency and duration) under which consensus can
be preserved.

n
X

xi (t)ẋi (t)

i=1
n
X
X
=
uij (t)]
[xi (t)
i=1

=−

j∈Ni

X

Dij (t) signε (Dij (tij
k ))

{i,j}∈E:
ij
ij
|D ij (tij
k )|≥ε ∧ tk ∈Θ (0,t)

≤−

i

1:

(16)

ij
ij
Let tij
k := max{t` : t` ≤ t, ` ∈ Z≥0 }. First notice that the
derivative of V along the solutions to (2) satisfies

As it will become clear later on, this is in order to maximize
the robustness of the consensus protocol against DoS. By (14),
it is an easy matter to see that for each {i, j} ∈ E the sequences
{tij
k }k∈Z≥0 satisfy a “dwell-time” property, since
ε
ij
ij
(15)
∆ij
k := tk+1 − tk ≥
4dmax
for all k ∈ R≥0 , where dmax = maxi∈I d . This ensures that
all the sequences of transmission times are Zeno-free.
For the sake of clarity, the DoS-resilient consensus protocol
is summarized below.
DoS-resilient consensus protocol

1 >
x x
2

X
{i,j}∈E:
ij
ij
|D ij (tij
k )|≥ε ∧ tk ∈Θ (0,t)

|Dij (tij
k )|
2

(17)
In words, the derivative of V decreases whenever, for some
{i, j} ∈ E, two conditions are met: i) |Dij (tij
k )| ≥ ε, which
means that i and j are not ε-close; and ii) communication on
the link that connects i and j is possible. The third equality
follows from the fact that for any {i, j} ∈ E for which
ij
ij
ij
|Dij (tij
k )| < ε or tk ∈ Ξ (0, t) we have u (t) = 0 for all
ij ij
ij
[tk , tk+1 [, and the fact that u (t) = signε (Dij (tij
k )) where
Dij (t) = xj (t) − xi (t). The inequality follows from the fact
that, during the continuous evolution |Ḋij (t)| ≤ di + dj and at
the jumps Dij (t) does not change its value. This implies that
Dij (t) cannot differ from Dij (tij
k ) in absolute value for more
than (di + dj )(t − tij
).
Exploiting
this fact, if communication
k
is allowed and |Dij (tij
)|
≥
ε
then
by (5) and (14) we have
k
|Dij (t)| ≥ |Dij (tij
k )|/2

(18)

signε (Dij (t)) = signε (Dij (tij
k ))

(19)

and

ij
for all [tij
k , tk+1 [.
From (17) there must exist a finite time T∗ such that, for
every {i, j} ∈ E and every k with tij
k ≥ T∗ , it holds that
ij
ij
|Dij (tij
)|
<
ε
or
t
∈
Ξ
(0,
t).
This
is because, otherwise,
k
k
V would become negative. The proof follows recalling that in
ij
ij
both the cases |Dij (tij
k )| < ε and tk ∈ Ξ (0, t) the control
ij
u (t) is set equal to zero.

The above result does not allow one to conclude anything
about the final disagreement vector in the sense that given a
pair of nodes (i, j) the asymptotic value of |xj (t) − xi (t)| can
be arbitrarily large. As an example, if node i is never allowed
to communicate then xi (t) = xi (0) for all t ∈ R≥0 . In order
to recover the same conclusions as in Theorem 1, bounds on
DoS frequency and duration have to be enforced. The result
which follows provides one such characterization.

SENEJOHNNY et al.: A JAMMING-RESILIENT ALGORITHM FOR SELF-TRIGGERED NETWORK COORDINATION

Let {i, j} ∈ E be a generic network link, and consider a
DoS sequence on {i, j}, which satisfies Assumption 1 and 2.
Define
αij :=

1
τdij

+

∆ij
∗

(20)

τfij

where
∆ij
∗ :=

2(di

ε
+ dj )

(21)

Proposition 2 (Link Persistency-of-Communication (PoC)):
Consider any link {i, j} ∈ E employing the transmission
protocol (13). Also consider any DoS sequence on {i, j},
which satisfies Assumption 1 and 2 with η ij and κij arbitrary,
and τdij and τfij such that αij < 1. Let
Φij :=

κij + (η ij + 1)∆ij
∗
1 − αij

(22)

Then, for any given unsuccessful transmission attempt tij
k , at
least one successful transmission occurs over the link {i, j}
ij
ij
within the interval [tij
k , tk + Φ ].
Proof. In order to maintain continuity, a proof of this result
is reported in Appendix.

We refer to the property above as a PoC condition since this
property guarantees that DoS does not permanently destroy
communication. Combining Proposition 1 and 2, the main
result of this section can be stated.
Theorem 2 (δ-consensus): Let x be the solution to (2) and
(13). For each {i, j} ∈ E, consider any DoS sequence that
satisfies Assumption 1 and 2 with η ij and κij arbitrary, and
τdij and τfij such that αij < 1. Then, for every initial condition,
x converges in finite time to a point x∗ belonging to the set
E as in (7).
Proof. By Proposition 1, all the local controls become zero
in a finite time T∗ . In turns, Proposition 2 excludes that this
is due to the persistence of a DoS status. This means that, for
all {i, j} ∈ E, |Dij (t)| = |xj (t) − xi (t)| < ε for all t ≥ T∗ .
Since each pair of neighboring nodes differs by a most ε and
the nominal graph is connected, we conclude that each pair of
network nodes can differ by at most δ = ε(n − 1).

C. Convergence time
The above theorem shows that convergence is reached in
a finite time. The following result characterizes the effect of
DoS on the convergence time.
Lemma 1 (Bound on the convergence time): Consider the
same assumptions as in Theorem 1. Then,
X

1
dmax
4dmax
T∗ ≤
+
+ 2 Φ
(xi (0))2
(23)
ε εdmin
ε
i∈I

i

where dmin := mini∈I d and Φ := max{i,j}∈E Φij .
Proof. Consider the same Lyapunov function V as in the
proof of Proposition 1. Notice that, by construction of the
control law and the scheduling policy, for every successful
ij ij
transmission tij
k characterized by |D (tk )| ≥ ε, the function
V decreases with rate not less than ε/2 for at least ε/(4dmax )

5

units of time. Hence, V decreases by a least ε2 /(8dmax ) := ε∗ .
Considering all the network links, such transmissions are in
total no more than bV (0)/ε∗ c since, otherwise, the function V
would become negative. Hence, it only remains to compute the
time needed to have bV (0)/ε∗ c of such transmissions. In this
respect, pick any t∗ ≥ 0 such that consensus has still not be
reached. Note that we can have uij (t∗ ) = 0 for all {i, j} ∈ E.
However, this condition can last only for a limited amount
of time. In fact, if uij (t∗ ) = 0 then the next transmission
attempt, say `ij , over the link {i, j} will necessarily occur at
ij
a time less than or equal to t∗ + ∆ij
∗ with ∆∗ ≤ ε/(4dmin ).
Let Q := [t∗ , t∗ + ε/(4dmin )], and suppose that over Q all the
controls uij have remained equal to zero. This implies that for
some {i, j} ∈ E we necessarily have that `ij is unsuccessful.
This is because if uij (t) = 0 for all {i, j} ∈ E and all t ∈ Q
then xi (t) = xi (t∗ ) for all i ∈ I and all t ∈ Q. Hence, if all
the `ij were successful, we should also have uij (`ij ) 6= 0 for
some {i, j} ∈ E since, by hypothesis, consensus is not reached
at time t∗ . Hence, applying Proposition 2 we conclude that at
least one of the controls uij will become non zero before
`ij + Φij units of time have elapsed. Overall, this implies that
at least one control will become nonzero before ε/(4dmin ) + Φ
units of time have elapsed. Since t∗ is generic, we conclude
that V decreases by at least ε∗ every ε/(4dmax )+ε/(4dmin )+Φ
units of time, which implies that


ε
V (0)
ε
+
+Φ
(24)
T∗ ≤
4dmax
4dmin
ε∗
The thesis P
follows by recalling that V (0) can be rewritten as
V (0) = 12 i∈I (xi (0))2 .

V. D ISCUSSION AND EXTENSIONS
A. Persistency-of-Communication and consensus under permanent link disconnections
As it follows from the foregoing analysis, consensus is
achieved whenever for each link {i, j} ∈ E, the DoS signal
satisfies αij < 1. This condition poses limitations on both
DoS frequency and duration. It is worth noting that this
condition is in a wide sense also necessary in order to achieve
consensus. To see this, consider a network for which removing
the link {i, j} causes the network underlying graph to be
disconnected. Of course, if communication over {i, j} is
always denied then consensus cannot be achieved for arbitrary
initial conditions. In this respect, it is an easy matter to see that
condition αij < 1 becomes necessary to achieve consensus.
In fact, denote by S(τfij , τdij ) the class of all DoS signals for
which αij ≥ 1. Then, S(τfij , τdij ) does always contain DoS
signals for which communication over the link {i, j} can be
permanently denied. As an example, consider the DoS signal
ij
ij
characterized by (hij
n , τn ) = (tk , 0). This DoS signal satisfies
ij
Assumption 1 and 2 with (η , κij , τfij , τdij ) = (1, 0, ∆ij
∗ , ∞),
but destroys any communication attempt over the link {i, j}.
As another example, consider the DoS signal characterized by
ij
(hij
0 , τ0 ) = (0, ∞). This signal satisfies Assumption 1 and 2
with (η ij , κij , τfij , τdij ) = (1, 0, ∞, 1), but, as before, destroys
any communication attempt over the link {i, j}. In both the
examples, αij = 1.

6

Requiring αij < 1 is not surprising. In fact, the fulfillment
of this condition requires that
τfij > ∆ij
∗

and τdij > 1

(25)

The first requirement, τfij > ∆ij
∗ , simply means that DoS can
occasionally occur at a rate faster than the highest transmission
rate of the link {i, j}. However, on the average, the frequency
at which DoS can occur must be sufficiently small compared
to sampling rate of the network link. Likewise, the second
requirement, τdij > 1, simply means that, on the average, the
amount of DoS affecting link {i, j} must necessarily be a
fraction of the total time. PoC can be therefore regarded as an
average connectivity property.
It is worth noting that in some cases consensus can be
preserved even if αij ≥ 1 for certain network links. This
happens whenever removing such links does not cause the
graph to de disconnected. More precisely, let X be any set of
links such that GX := (I, E \ X ) remains connected. From the
foregoing analysis, it is immediate to conclude that consensus
is preserved whenever αij < 1 for all {i, j} ∈ E \ X , even
if communication over the links {i, j} ∈ X is permanently
denied.
B. Comparison with classic connectivity conditions
As previously noted, PoC can be regarded as an average
connectivity property as it does not require graph connectivity point-wise in time. In this sense, it is reminiscent
of Persistency-of-Excitation conditions that are found in the
literature on consensus under switching topologies (e.g., see
[21]). There are, however, noticeable differences. To see this,
consider the simple situation in which the Dos pattern is
ij
the same for all the links, i.e., (hij
n , τn ) = (hn , τn ) for all
{i, j} ∈ E and all n ∈ Z≥0 . Under such circumstances,
the incidence matrix of the graph is a time-varying matrix
satisfying: i) D(t) = 0 in the presence of DoS; and ii)
D(t) = D in the absence of DoS, where D represents the
incidence matrix related to the nominal graph configuration.
Consider now a DoS pattern consisting of countable number
of singletons, i.e., Hn = {hn } for all n ∈ Z≥0 . In a classic
continuous-time setting, such a DoS pattern does not destroy
consensus. In fact, it is trivial to conclude that there exist
constants c1 , c2 ∈ R>0 such that (cf. [21])
Z t0 +c1
QD(t)D> (t)Q> dt = QDD> Q> c1 > c2 I
(26)
t0

for all t0 ∈ R≥0 , where Q is a suitable projection matrix
such that QD(t)D> (t)Q> is nonsingular if and only if the
graph induced by D(t) is connected. In the present case,
in accordance with the previous discussion, consensus can
instead be destroyed. The subtle, yet important, difference
is due to the constraint on the frequency of the information
exchange that is imposed by the network. In this sense, the
notion of PoC naturally extends the Persistency-of-Excitation
condition to digital networked settings by requiring that the
graph connectivity be established over periods of time that
are consistent with the maximum transmission rate imposed
by the communication protocol.

C. Accounting for genuine DoS
In the foregoing analysis, we focused on the case where
DoS is caused by malicious attacks. Of course, DoS might
also result from a “genuine” network congestion. Hereafter,
we will briefly discuss how the case of genuine DoS can be
incorporated into the present framework. We shall focus on a
deterministic formulation of the problem. A probabilistic characterization of the problem, though restricted to a centralized
setting, has been proposed in [28].
Let β ij ∈ [0, 1] be an upperbound on the average percentage
of transmission failures that can occur over the link {i, j}. This
bound can be chosen as representative of the situation where
all the network nodes exchange information at the highest
transmission rate (according to (14), this is equal to 4dmax /ε
for each link). Here. by “average” we mean that, denoting by
TAij (τ, t) and TFij (τ, t) the number of transmission attempts
and transmission failures for the link {i, j} on the interval
[τ, t], it holds that
TFij (τ, t)
TAij (τ, t)

≤ β ij

(27)

as TAij (τ, t) → ∞.
This condition can be suitably rearranged. To this end, first
notice that the above condition is equivalent to the existence
of a positive constant aij such that
TFij (τ, t) ≤ aij + β ij TAij (τ, t)

(28)

for all t, τ ∈ R≥0 with t ≥ τ . Moreover, it holds that
ij
TAij (τ, t) ≤ d(t − τ )/∆ij
∗ e since, by construction, ∆∗ is the
smallest inter-transmission time for the link {i, j}. Letting
bij := aij + 1, we then have
TFij (τ, t) ≤ bij +

t−τ
ij
(∆ij
∗ /β )

(29)

Therefore, we can regard genuine transmission failures as the
result of a DoS signal in the form of a train of pulses that
are superimposed to the transmission instants, where TFij (τ, t)
coincides with the number nij (τ, t) of DoS off/on transitions
occurring on the interval [τ, t]. Thus, Assumption 1 and 2
ij
are satisfied with (η ij , κij , τfij , τdij ) = (bij , 0, ∆ij
∗ /β , ∞).
According to the analysis of Section IV, one can conclude
the following: i) if only genuine transmission failures are
present (no malicious DoS), Persistency-of-Communication is
preserved as long as
1
τdij

+

∆ij
∗
τfij

= β ij < 1

(30)

This is consistent with intuition and, in fact, simply means
that communication over the link {i, j} is not permanently
destroyed if and only if TFij (τ, t) < TAij (τ, t) on the average;
ii) in case of genuine and malicious transmission failures,
one can simply consider two independent DoS signals acting
on the same link, each one characterized by its own 4-tuple
(η ij , κij , τfij , τdij ). It is immediate to see that that the analysis
of Section IV carries over to the present case by replacing
condition αij < 1 with αij + β ij < 1.

1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

x(t)

x(t)

SENEJOHNNY et al.: A JAMMING-RESILIENT ALGORITHM FOR SELF-TRIGGERED NETWORK COORDINATION

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0

7

0
0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

0

0.05

0.1

0.15

time(sec)

0.2

0.25

0.3

0.35

0.4

0.45

0.5

time(sec)

Fig. 1. Evolution of x, corresponding to the solution to (2) and (13) for a
random graph with n = 40 nodes in the absence of DoS.

Fig. 2. Evolution of x, corresponding to the solution to (2) and (13) for a
random graph with n = 40 nodes in the presence of DoS.

TABLE I
D O S AVERAGE DUTY CYCLE OVER SOME LINKS
Link {i, j}
{13, 14}
{34, 39}
{9, 21}

Duty cycle (%)
49 %
55.96 %
52.76 %

Link {i, j}
{6, 34}
{9, 26}
{33, 38}

Duty cycle (%)
44.78 %
47.3 %
58.96 %

1

1

0.5

0.5

0

0
0

VI. A NUMERICAL EXAMPLE
We consider a random connected undirected graph with n =
40 nodes and with di = 4 for all i ∈ I. Nodes and control
initial values are generated randomly within the interval [0, 1]
and the set {−1, 0, 1}, respectively.
We consider the behavior of (2) and (13) with ε = 0.005.
Figure 1 depicts simulation results for the nominal case in
which DoS is absent. Notice that in this case (13) coincides
with (4). We next consider the case in which DoS is present.
Simulation results are reported in Figure 2. In the simulation,
we considered DoS attacks which affect each of the network
links independently. For each link, the corresponding DoS
pattern takes the form of a pulse-width modulated signal with
variable period and duty cycle (maximum period of 0.15sec
and maximum duty cycle equal to 100%), both generated
randomly. These patterns are reported in Table I and depicted
in Figure 3 for a few number of network links. Notice that,
for each DoS pattern, one can compute corresponding values
for (η ij , κij , τfij , τdij ). They can be determined by computing
the values nij (τ, t) and |Ξij (τ, t)| of each DoS pattern (cf.
Assumption 1 and 2) over the considered simulation horizon.
Figure 4 depicts the obtained values of τfij and τdij for each
{i, j} ∈ E. One sees that these values are consistent with the
requirements imposed by the PoC condition.
VII. C ONCLUDING REMARKS
We investigated self-triggered coordination for distributed
network systems in the presence of Denial-of-Service at the
communication links, of both genuine and malicious nature.
We considered a general framework in which DoS can affect
each of the network links independently, which is relevant for

0.1

0.2

0.3

0.4

0.5

1

1

0.5

0.5

0

0

0.1

0.2

0.3

0.4

0.5

0

0.1

0.2

0.3

0.4

0.5

0

0.1

0.2

0.3

0.4

0.5

0
0

0.1

0.2

0.3

0.4

0.5

1

1

0.5

0.5

0

0
0

0.1

0.2

0.3

time(sec)

0.4

0.5

time(sec)

Fig. 3. DoS pattern for the network links {13, 14}, {6, 34}, {34, 39},
{9, 26}, {9, 21} and {33, 38}. The vertical gray stripes represent the timeintervals over which DoS is active.

networks operating in peer-to-peer mode. By introducing a
notion of Persistency-of-Communication (PoC), we provided
an explicit characterization of DoS frequency and duration
under which consensus can be preserved by suitably designing
time-varying control and communication policies. An explicit
characterization of the effects of DoS on the consensus time
has also been provided. We compared the notion of PoC with
classic average connectivity conditions that are found in pure
continuous-time consensus networks. The analysis reveals that
PoC naturally extends such classic conditions to a digital
networked setting by requiring graph connectivity over periods
of time that are consistent with the constraints imposed by the
communication medium.
The present results lend themselves to many extensions.

8

ij
However, condition |Θ̄(tij
k , t∗ + ∆∗ )| = 0 is not possible. To
see this, simply notice that

0.07

ij
ij
|Θ̄(tij
k , t)| = t − tk − |Ξ̄(tk , t)|

0.06

ij
ij
ij
≥ t − tij
k − |Ξ(tk , t)| − (n(tk , t) + 1)∆∗

0.05

ij
ij
ij
ij
≥ (t − tij
k )(1 − α ) − κ − (η + 1)∆∗ (34)
0.04

τf

for all t ≥ tij
k where the first inequality follows from the
definition of the set Ξ̄(τ, t) while the second one follows from
Assumption 1 and 2. Hence, by (34), we have |Θ̄(tij
k , t)| > 0
ij
ij −1 ij
ij
ij
for all t > tij
+
(1
−
α
)
(κ
+
(η
+
1)∆
)
=
tij
∗
k
k +Φ .
ij
ij
Accordingly, |Θ̄(tk , t∗ + ∆∗ )| = 0 cannot occur because t∗ +
ij
ij
∆ij
∗ > tk + Φ . In fact, by hypothesis, t∗ is defined as the
ij
ij
last unsuccessful transmission attempt within [tij
k , tk + Φ ],
and, by (14), the next transmission attempt after t∗ occurs at
time t∗ + ∆ij

∗ . This concludes the proof.

0.03
0.02
0.01
0
1

1.2

1.4

1.6

1.8

2

2.2

2.4

2.6

2.8

τd

Fig. 4. Locus of the points 1/τd + ∆∗ /τfij = 1 as a function of (τd , τf )
with ∆∗ = X (blue solid line). Notice that ∆∗ = ∆ij
∗ for all {i, j} ∈ E,
so that the locus of point does not vary with {i, j}. The various ∗ represent
the values of (τdij , τfij ) for the network links.

Most notably, it is interesting to investigate whether the present
results can be extended to coordination problems involving
higher-order nodes dynamics. Another interesting investigation
pertains the analysis of coordination schemes in the presence
of both DoS and deceptive attacks.
A PPENDIX
Proof of Proposition 2. Consider any link {i, j} ∈ E, and
suppose that a certain transmission attempt tij
k is unsuccessful.
We claim that a successful transmission over {i, j} does
ij
ij
always occur within [tij
k , tk + Φ ]. We prove the claim by
contradiction. To this end, we first introduce some auxiliary
ij
ij
ij
ij
quantities. Let H̄nij := {hij
n } ∪ [hn , hn + τn + ∆∗ [. denote
the n-th DoS interval over the link {i, j} prolonged by ∆ij
∗
units of time. Also let
[
\
Ξ̄ij (τ, t) :=
H̄nij
[τ, t]
(31)
n∈Z≥0

Θ̄ij (τ, t) := [τ, t] \ Ξ̄ij (τ, t)

(32)

Suppose then that the claim is false, and let t∗ denote the
ij
ij
last transmission attempt over [tij
k , tk + Φ ]. Notice that this
ij
necessarily implies |Θ̄ij (tk , t∗ )| = 0. To see this, first note
that, in accordance with (14), the inter-sampling time over the
ij
i
j
interval [tij
k , t∗ ] is equal to ε/(2(d + d )) = ∆∗ . Hence,
ij
we cannot have |Θ̄ij (tk , t∗ )| > 0 since this would imply
the existence of a DoS-free interval within [tij
k , t∗ ] of length
greater than ∆ij
∗ , which is not possible since, by hypothesis,
no successful transmission attempt occurs within [tij
k , t∗ ]. Thus
|Θ̄ij (tij
,
t
)|
=
0.
Moreover,
since
t
is
unsuccessful,
it
∗
∗
k
must be contained in a DoS interval, say Hqij . This implies
ij
[t∗ , t∗ + ∆ij
∗ [⊆ H̄q Hence,
ij
ij
ij
|Θ̄(tij
k , t∗ + ∆∗ )| = |Θ̄(tk , t∗ )| + |Θ̄(t∗ , t∗ + ∆∗ )|

=0

(33)

R EFERENCES
[1] H. Sandberg, S. Amin, and K. Johansson, “Cyberphysical security
in networked control systems: An introduction to the issue,” Control
Systems, IEEE, vol. 35, no. 1, pp. 20–23, 2015.
[2] A. A. Cardenas, S. Amin, and S. Sastry, “Secure control: Towards survivable cyber-physical systems,” in The 28th International Conference
on Distributed Computing Systems Workshops, 2008, pp. 495–500.
[3] H. Fawzi, P. Tabuada, and S. Diggavi, “Secure state-estimation for dynamical systems under active adversaries,” in Communication, Control,
and Computing (Allerton), 2011 49th Annual Allerton Conference on,
2011, pp. 337–344.
[4] F. Pasqualetti, F. Dorfler, and F. Bullo, “Control-theoretic methods for
cyberphysical security: Geometric principles for optimal cross-layer
resilient control systems,” Control Systems, IEEE, vol. 35, no. 1, pp.
110–127, 2015.
[5] W. Xu, K. Ma, W. Trappe, and Y. Zhang, “Jamming sensor networks:
attack and defense strategies,” Network, IEEE, vol. 20, no. 3, pp. 41–47,
2006.
[6] D. Thuente and M. Acharya, “Intelligent jamming in wireless networks
with applications to 802.11 b and other networks,” in Proc. 25th
IEEE Communications Society Military Communications Conference
(MILCOM06), Washington, DC, 2006, pp. 1–7.
[7] S. Amin, A. Càrdenas, and S. Sastry, “Safe and secure networked
control systems under denial of-service attacks,” In Hybrid systems:
Computation and Control, pp. 31–45, 2009.
[8] A. Gupta, C. Langbort, and T. Basar, “Optimal control in the presence
of an intelligent jammer with limited actions,” in Proc. of the IEEE
Conference on Decision and Control, 2010, pp. 1096–1101.
[9] G. Befekadu, V. Gupta, and P. Antsaklis, “Risk-sensitive control under
a class denial-of-service attack models,” in 2011 American Control
Conference, San Francisco, CA, USA, 2011.
[10] A. Teixeira, I. Shames, H. Sandberg, and K. H. Johansson, “A secure control framework for resource-limited adversaries,” Automatica,
vol. 51, pp. 135–148, 2015.
[11] H. S. Foroush and S. Martı́nez, “On event-triggered control of linear
systems under periodic denial-of-service jamming attacks,” in Proc. of
the IEEE Conference on Decision and Control, 2012, pp. 2551–2556.
[12] C. De Persis and P. Tesi, “Resilient control under denial-of-service,”
arXiv preprint arXiv:1311.5143, 2013.
[13] ——, “Input-to-state stabilizing control under denial-of-service,” IEEE
Transactions on Automatic Control, vol. 60, pp. 2930–2944, 2015.
[14] ——, “On resilient control of nonlinear systems under denial-ofservice,” in Proc. of the IEEE Conference on Decision and Control,
2014, pp. 5254–5259.
[15] C. De Persis and P. Frasca, “Robust self-triggered coordination with
ternary controllers,” Automatic Control, IEEE Transactions on, vol. 58,
no. 12, pp. 3024–3038, 2013.
[16] J. Cortés, “Finite-time convergent gradient flows with applications to
network consensus,” Automatica, vol. 42, no. 11, pp. 1993–2000, 2006.
[17] W. Xu, W. Trappe, Y. Zhang, and T. Wood, “The feasibility of launching
and detecting jamming attacks in wireless networks,” in Proceedings of
the 6th ACM international symposium on Mobile ad hoc networking and
computing. ACM, 2005, pp. 46–57.

SENEJOHNNY et al.: A JAMMING-RESILIENT ALGORITHM FOR SELF-TRIGGERED NETWORK COORDINATION

[18] P. Tague, M. Li, and R. Poovendran, “Mitigation of control channel
jamming under node capture attacks,” Mobile Computing, IEEE Transactions on, vol. 8, no. 9, pp. 1221–1234, 2009.
[19] D. Senejohnny, P. Tesi, and C. De Persis, “Self-triggered coordination
over a shared network under denial-of-service,” in Proc. of the IEEE
Conference on Decision and Control, Osaka, Japan, 2015.
[20] R. Olfati-Saber and R. M. Murray, “Consensus problems in networks
of agents with switching topology and time-delays,” Automatic Control,
IEEE Transactions on, vol. 49, no. 9, pp. 1520–1533, 2004.
[21] M. Arcak, “Passivity as a design tool for group coordination,” Automatic
Control, IEEE Transactions on, vol. 52, no. 8, pp. 1380–1390, 2007.
[22] A. Jadababaie, J. Lin, and A. Morse, “Coordination of groups of mobile
autonomous agents using nearest neighbour rules,” IEEE Trans. Automat.
Contr, vol. 48, no. 6, pp. 988–1001, 2003.
[23] P. M. M. Velasco and J. Fuertes, “The self-triggered task model for realtime control systems,” in Proceedings of 24th IEEE Real-Time Systems
Symposium, Work-in-Progress Session, 2003.
[24] J. Bellardo and S. Savage, “802.11 denial-of-service attacks: Real
vulnerabilities and practical solutions.” in USENIX security, 2003, pp.
15–28.
[25] K. Pelechrinis, M. Iliofotou, and S. V. Krishnamurthy, “Denial of service
attacks in wireless networks: The case of jammers,” Communications
Surveys & Tutorials, IEEE, vol. 13, no. 2, pp. 245–257, 2011.
[26] B. DeBruhl and P. Tague, “Digital filter design for jamming mitigation in
802.15. 4 communication,” in Computer Communications and Networks
(ICCCN), 2011 Proceedings of 20th International Conference on, 2011,
pp. 1–6.
[27] A. D. Wood, J. Stankovic et al., “Denial of service in sensor networks,”
Computer, vol. 35, no. 10, pp. 54–62, 2002.
[28] A. Cetinkaya, H. Ishii, and T. Hayakawa, “Event-triggered control over
unreliable networks subject to jamming attacks,” arXiv:1403.5641, 2015.

9

