arXiv:1505.07158v2  [cs.SY]  16 Mar 2016
1
Resilient and Decentralized Control of Multi-level Cooperative Mobile
Networks to Maintain Connectivity under Adversarial Environment
Juntao Chen and Quanyan Zhu
Department of Electrical and Computer Engineering, Tandon School of Engineering
New York University, Brooklyn, 11201, USA. E-mail: {jc6412, qz494}@nyu.edu.
Abstract—Network connectivity plays an important role in the
information exchange between different agents in the multi-level
networks. In this paper, we establish a game-theoretic framework
to capture the uncoordinated nature of the decision-making at
different layers of the multi-level networks. Specifically, we design
a decentralized algorithm that aims to maximize the algebraic
connectivity of the global network iteratively. In addition, we
show that the designed algorithm converges to a Nash equilibrium
asymptotically and yields an equilibrium network. To study
the network resiliency, we introduce three adversarial attack
models and characterize their worst-case impacts on the network
performance. Case studies based on a two-layer mobile robotic
network are used to corroborate the effectiveness and resiliency
of the proposed algorithm and show the interdependency between
different layers of the network during the recovery processes.
I. INTRODUCTION
Teams of mobile cooperative robots have a wide range
of applications, such as rescue, monitoring, and searching in
space exploration. One of the challenges in this kind of mobile
robotic network (MRN) is to maintain the connectivity be-
tween robots, since a higher connectivity enables faster infor-
mation spreading and hence a high level of situational aware-
ness. Connectivity control of the MRN has been addressed in
a number of previous works including [1, 2, 3] which have
successfully tackled a single network of cooperative robots.
Recent advances in networked systems have witnessed emerg-
ing applications involving multi-layer networks or network-of-
networks [4, 5]. For example, when unmanned aerial vehicles
(UAVs) and unmanned ground vehicles (UGVs) execute tasks
together, the whole network can be seen as a two-layer
interdependent network as shown in Fig. 1. Another example
is the complex networks including mobile vehicular network
and communication networks in public infrastructures. The
interaction between mobile vehicles needs the support from
communication network thus making two networks coupled.
Therefore, the current single network control paradigm is not
sufficient yet to address new challenges related to the analysis
and design of multi-layer mobile networks.
The main objective of this work is to develop a theoretic
framework that can capture the interactions between robots
within a network and across networks. In our problem setting,
each layer of the robotic network aims to maximize the
connectivity of the overall network. If the whole network
is fully cooperative or governed by a single agent, then the
designed network is a team-optimal solution. However, in
practice, different layers of robotic networks are often operated
by different entities, which makes the coordination between
separate entities difficult. For example, in the previous UAV
UAV 
network 
UGV 
network
Intra-link
Interlink
Interlink
G1
G2
Fig. 1.
Two-layer mobile robotic networks. One network consists of 5 UAVs,
and the other network consists of 6 UGVs.
and UGV two-layer networks in Fig. 1, though the objectives
for two networks are aligned, UAV is operated by the air
force while UGV is operated by the army, which could lead to
insufficient coordination. To address this problem, we establish
a game-theoretic model in which two players control robots to
maximize the global connectivity independently. This frame-
work captures the lack of coordination between players in the
multi-level networks. Furthermore, it guides the algorithmic
design of decentralized mechanism for achieving an equilib-
rium solution that is close to the team-optimal solution. In
this paper, two players update their own robotic configuration
based on the current one to maximize the network connectivity.
This generates an iterative algorithm which converges to a
Nash equilibrium (NE) point asymptotically and yields an
equilibrium MRN.
An MRN is prone to adversarial attacks since a robot can
be controlled by an adversary [6, 7], and the communication
links between robots can be jammed [8, 9, 10]. Therefore, re-
silient control of the multi-level robotic networks to malicious
attacks is critical to enhance its resiliency. To this end, we
model the mobility of the robots by taking into account the
communication links within and across the networks and use
a game-theoretic approach to develop a resilient and decen-
tralized algorithm for the individual networks. To study the
network resiliency, we consider three attack models including
the global positioning system (GPS) spoofing attack, targeted
jamming attack and denial-of-service (DoS) attack. The impact
of each attack can be quantified by measuring the difference of
the algebraic connectivity of the network under a certain type
of attack and without attacks. In addition, we characterize the
worst-case of each attack and identify the interdependencies
that exist in the multi-level networks. Case studies show that
the robot removal resulting from the DoS attack will lead to
the largest decrease in the network connectivity, and the MRN
is the most resilient to the GPS spoofing attack which results
in the constrained physical movement of robots by using the
proposed control method. Furthermore, robots in the network
2
without attacks will respond by moving to the positions that
can set up the most communication links with the robots in
the attacked network during the recovery processes, and this
shows the interdependency in the multi-level networks.
The contributions of this paper are summarized as follows:
1) We establish a game-theoretic framework that enables a
decentralized control of mobile robots in the multi-level
networks.
2) We introduce three attack models to the network and
characterize their worst-case scenarios. In addition, we
design a resilient and decentralized algorithm that aims to
maximize the algebraic connectivity of the global MRN.
3) We show the convergence of the designed algorithm to a
NE asymptotically, and corroborate its effectiveness and
resiliency by case studies. The existence of interdepen-
dency in the multi-level MRN is also verified.
A. Related Work
In the previous works, robotic network connectivity control
problem is often addressed either in a totally centralized way
[1, 2, 11, 12], or completely decentralized way [3, 13, 14].
The centralized framework yields an optimal network but with
low resiliency, since responses to failures in a global network
may not be instantaneous. The network resulting from the
decentralized framework is resilient; however, it is difficult
to achieve the team solution with limited coordination. Our
framework stands in between these two frameworks and thus
leads to balanced features in terms of resiliency and optimality.
B. Organization of the Paper
The rest of the paper is organized as follows: Section II
presents some basics of graph theory and interdependent
networks. We formulate a multi-level network formation game
problem in Section III. System dynamics discretization and
the equilibrium solution concept is presented in Section IV. A
semidefinite programming approach and an iterative algorithm
are proposed in Section V. Section VI introduces three types
of attacks to the MRN and characterizes their corresponding
worst-case conditions. Case studies are given in Section VII,
and Section VIII concludes the paper.
II. BACKGROUND AND INTERDEPENDENT
NETWORK MODEL
Let G(V, E) be an undirected graph composed by a set
V of n nodes and a set E of m links with n = |V |, and
m = |E|. For a link e ∈E connecting nodes i and j where
the link weight is equal to wij, we define two vectors ae ∈Rn
and be ∈Rn, where ae(i) = 1, ae(j) = −1, be(i) = wij,
be(j) = −wij, and other entries 0. Then, the Laplacian matrix
L of network G can be expressed as
L =
m
X
e=1
aebT
e .
(1)
Basically, for the weighted Laplacian matrix L, its diagonal
entries are equal to Lii = P
j∈Ni wij, ∀i ∈V , where Ni
denotes the set of nodes that are connected to node i. In
addition, Lij = −wij if nodes i and j are connected, for
i ̸= j ∈V , and 0 otherwise. Note that wij = wji, ∀i, j ∈V .
By ordering the eigenvalues of L in an increase way, we obtain
0 = λ1 ≤λ2 ≤... ≤λn,
(2)
where λ2(L) is called algebraic connectivity of G. In addition,
the Fiedler vector of a network refers to the eigenvector
associated with the eigenvalue λ2(L) [15].
For a two-layer interdependent network, we define two
networks G1(V1, E1) and G2(V2, E2), where network 1 and
network 2 are represented by Gi, for i = 1, 2, respectively.
Network i, i ∈{1, 2}, is composed of ni = |Vi| nodes
and mi = |Ei| links. The global network resulting from
the connection of these two networks can be represented by
G = (V1 ∪V2, E1 ∪E2 ∪E12), where E12 is a set of
intra-links between G1 and G2. For convenience, we denote
the network consisting of the intra-links between G1 and G2
as G12. The adjacency matrix A of the global network G has
the entry
aij =
(
wij, nodes i and j are connected;
0, nodes i and j are not connected.
Let A1 ∈Rn1×n1 and A2 ∈Rn2×n2 be the adjacency matrices
of G1 and G2, respectively, and n = n1 +n2. When E12 ̸= ∅,
the adjacency matrix A ∈Rn×n takes the following form
A =
 A1
B12
BT
12
A2

,
where B12 ∈Rn1×n2 is a matrix used to capture the effect
of intra-links between networks. Define two diagonal matrices
D1 ∈Rn1×n1 and D2 ∈Rn2×n2 as
(D1)ii =
X
j
(B12)ij, (D2)ii =
X
j
(BT
12)ij.
Then, by using L = D −A, we obtain the Laplacian matrix
L =
L1 + D1
−B12
−BT
12
L2 + D2

,
(3)
where L1 and L2 are the Laplacians corresponding to A1 and
A2, respectively.
Remark 1: The above formulated two-layer interdependent
framework can be easily extended to multi-layer cases.
III. PROBLEM FORMULATION
In this section, we formulate a two-level mobile robotic
network formation problem using a game-theoretic framework.
A. Two-level Network Formation Game
The position of robots in the network is denoted by a vector
x(t) =
x1(t), x2(t), ..., xn(t)


∈R3×n, and the dynamic of
each robot i is given by ˙xi(t) = ui(t), where ui(t) ∈R3 is
the control of robot i at time t. Besides, robots in the network
can exchange data via wireless communications. Denote the
communication link between robots i and j as (i, j). Then, the
strength of the communication link (i, j) can be captured by
the weight of the link. Thus, we can assign a weight function
3
w : R3 × R3 →R+ to each communication link (i, j), such
that
wij(t) = w
xi(t), xj(t)


= g(∥xij(t) ∥2),
for some g : R+ →R+, where xij(t) := xi(t) −xj(t). The
strength of a communication link decays exponentially with
the distance [16]. Therefore, the entries Aij of the adjacency
matrix A admit
Aij =







1,
∥xij(t) ∥2< ρ1;
e
−α(∥xij(t)∥2−ρ1)
ρ2−ρ1
,
ρ1 ≤∥xij(t) ∥2≤ρ2;
0,
∥xij(t) ∥2> ρ2,
(4)
for ρ1, ρ2 ∈R+, and ρ1 < ρ2. When the distance between the
robots is less than ρ1, the connectivity strength is up to 1; and
when the distance is larger than ρ2, robots lose the connection.
The model of a two-layer MRN is similar to the one in Fig.
1. Robots in the upper layer belong to network G1, and robots
in the bottom layer belong to network G2. For convenience,
we label robots in G1 as 1, 2, ..., n1 ∈V1, and robots in G2
as n1 + 1, n1 + 2, ..., n1 + n2 ∈V2. In addition, robots in
the same layer and various layers can communicate with each
other, and these communication links are called inter-links and
intra-links, respectively. Note that exchanging data between
robots in different layers is more difficult than that of the
robots in the same layer due to much longer distance. Thus,
to enable the information exchange between G1 and G2, we
assume that the communication strength of intra-links has a
larger value of ρ1 and ρ2 comparing with that of inter-links.
For simplicity, define −γ ≜{1, 2} \ γ, where γ ∈{1, 2}.
We consider that two players, player 1 (P1) and player 2
(P2), play a network formation game. P1 controls robots
in network G1, and P2 controls robots in G2. Specifically,
P1 and P2 update their own mobile network iteratively by
controlling the robots’ positions which are denoted as x1
and x2, respectively. Note that x1 := (x1, ..., xn1) ∈R3×n1,
x2 := (xn1+1, ..., xn) ∈R3×n2, and x := (x1, x2). For each
update, Pγ’s strategy is based on the current configuration
of network G−γ. The objectives of players are aligned by
maximizing the algebraic connectivity of the whole network
G, λ2
LG(x)


, at every step. In addition, the action spaces
of P1 and P2 are denoted by X1 and X2, respectively, which
include all the possible network configurations. The set of pure
strategy profiles X := X1 × X2 is the Cartesian product of the
individual pure strategy sets. Besides, the utility function for
both players is λ2
LG(x)


: X →R+.
Remark 2: In general, the objectives of two players can
be different rather than maximize the algebraic connectivity
of the global network. However, in our problem setting, the
two teams of robots execute tasks collaboratively, and thus
they both aim to optimize the global network connectivity to
improve communications.
In the MRN formation game, one essential constraint is the
minimum distance between the robots in the same layer. With-
out this constraint, all robots in the same layer will converge
to one point finally which is unreasonable in reality. Thus, we
assign a minimum distance for robots in G1 and G2 denoted by
d1 and d2, respectively. Then, the network formation game can
be represented by two individual interdependent optimization
problems Qt
1 and Qt
2 as follows:
Qt
1 :
max
x1(t+τ1) λ2
LG(x(t + τ1))


s.t.
||xij(t + τ1)||2
2 ≥d1,
∀i, j ∈V1,
xj(t + τ1) = xj(t),
∀j ∈V2.
(5)
Qt
2 :
max
x2(t+τ2) λ2
LG(x(t + τ2))


s.t.
||xij(t + τ2)||2
2 ≥d2,
∀i, j ∈V2,
xj(t + τ2) = xj(t),
∀j ∈V1,
(6)
where V1 and V2 denote the sets of nodes in G1 and G2,
respectively, and τ1 ∈R+ and τ2 ∈R+ are the time constants
indicating the update frequency of the players. Note that τ1 and
τ2 can be different because of distinct sensing, detection, and
response capabilities of two mobile networks. Furthermore,
smaller τ1 and τ2 indicate a higher resilience of the network to
attacks, since a higher update frequency leads to faster system
recovery.
Remark 3: Note that the network formation game is played
repeatedly over time, and its structure is the same only with
different initial conditions in terms of the robots’ position. In
addition, at each stage of play, the game captured by Qt
1 and
Qt
2 can be characterized as a constrained potential game due
to the identical objective of two players [17].
IV. SYSTEM DYNAMICS DISCRETIZATION AND
EQUILIBRIUM SOLUTION CONCEPT
To address the MRN formation problem formulated in
Section III, we first analyze the fundamental network algebraic
connectivity maximization problem (ACMP). For a given
network G with n nodes, its algebraic connectivity can be
represented by
λ2(LG(x)) =
min
||z||2=1,z⊥1 zTLG(x)z
(7)
based on the Courant-Fischer theorem [18], where 1 is an n-
dimensional vector with all-one entries. In addition, the func-
tion λ2(LG(x)) is concave in LG(x). Therefore, the ACMP
maxx λ2(LG(x)) gives rise to convex optimization approaches
to deal with our MRN control problem. For the unconstrained
ACMP, we present the following theorem.
Theorem 1 ([19]). The network algebraic connectivity maxi-
mization problem maxx λ2(LG(x)) is equivalent to the follow-
ing:
max
x, α
α
s.t.
LG(x) ⪰α · (In −1
n11T ),
(8)
where α ∈R, and In is an n-dimensional identity matrix.
A. Discretization of the Dynamics
For each update of the robotic network, it is essentially not
continuous in time. Therefore, for simplicity, we discretize
the formulated problems Qt
1 and Qt
2 in the following. First,
we deal with the minimum distance constraint. By denoting
4
Zij(t) = ||xij(t)||2
2, and then differentiating ||xij(t)||2
2 with
respect to the time, we obtain [2]
2{ ˙xi(t) −˙xj(t)}T {xi(t) −xj(t)} = ˙Zij(t).
(9)
By using Euler’s first order method x(t) →x(k),
˙x(t) →
x(k+1)−x(k)
∆t
, where ∆t is the sample time, we rewrite (9) as
2{xi(k + 1) −xj(k + 1)}T {xi(k) −xj(k)}
= Zij(k + 1)+Zij(k).
(10)
Similarly, differentiating and discretizing weight wij yield
wij(k + 1) = wij(k) + ∂f(||xij||2)
∂||xij||2

k
{xij(k + 1) −xij(k)}.
(11)
Hence, we can obtain a discrete Laplacian matrix LG
x(k)


by using (11) which is presented in Section IV-B.
B. Problem Reformulation
Based on (8) and (10), and for given initial position vectors
x2(k) and x1(k) for P1 and P2, respectively, we can reformu-
late the problems Qt
1 and Qt
2 as follows:
eQk
1 :
max
x1(k+1), α1(k+1)
α1(k + 1)
s.t.
LG(k + 1) ⪰α1(k + 1) · (In −1
n11T ),
2{xi(k + 1) −xj(k + 1)}T {xi(k) −xj(k)}
= Zij(k + 1) + Zij(k),
||xij(k + 1)||2
2 ≥d1,
∀i, j ∈V1,
xj(k + 1) = xj(k),
∀j ∈V2,
(12)
eQk
2 :
max
x2(k+1), α2(k+1)
α2(k + 1)
s.t.
LG(k + 1) ⪰α2(k + 1) · (In −1
n11T ),
2{xi(k + 1) −xj(k + 1)}T {xi(k) −xj(k)}
= Zij(k + 1) + Zij(k),
||xij(k + 1)||2
2 ≥d2,
∀i, j ∈V2,
xj(k + 1) = xj(k),
∀j ∈V1,
(13)
where α1(k + 1) and α2(k + 1) are the scalar objectives of
eQk
1 and eQk
2, respectively.
In addition, we obtain the discrete Laplacian matrix LG(k+
1) by using (11), and its entries lG
ij(k + 1) are
lG
ij(k + 1) =

















−wij(k + 1),
if i ̸= j, (i, j) ∈E1 ∪E2;
−˜wij(k + 1),
if i ∈V1, j ∈V2, or j ∈V1, i ∈V2;
X
s̸=i,s∈V1
wis(k + 1) +
X
q̸=i,q∈V2
˜wiq(k + 1),
if i = j ∈V1;
X
s̸=i,s∈V2
wis(k + 1) +
X
q̸=i,q∈V1
˜wiq(k + 1),
if i = j ∈V2;
where wij, ∀(i, j) ∈E1 ∪E2, represent the weight of
interlinks inside G1 and G2, and ˜wij, ∀(i, j) ∈E12, denote
the weight of intra-links connecting G1 and G2.
C. Nash Equilibrium of the Game
For the formulated discretized MRN formation game, a
natural solution concept is Nash equilibrium (NE). Before
presenting the formal definition of NE, we first analyze the
impact of the players’ action on the network at each step.
Specifically, after P1 takes his action at step k, G1 and
G12 are reconfigured, where G12 is the network between
G1 and G2. We denote network G1 and G12 at stage k as
G1,k and G12,k, respectively. For simplicity, we further define
eG12,k := G1,k ∪G12,k, which is a shorthand notation for
the merged network. Then, network Gk can be expressed as
Gk = eG12,k ∪G2,k. Similarly, after P2 updates network G2 at
step k, the whole network Gk becomes Gk = eG21,k ∪G1,k,
where eG21,k := G2,k ∪G12,k. Then, the formal definition
of Nash equilibrium (NE) which depends on the position of
robots is as follows.
Definition 1 (Nash Equilibrium). The Nash equilibrium solu-
tion to the discretized multi-level robotic networks formation
game is a strategy profile x∗, where x∗= (x∗
1, x∗
2) ∈X, that
satisfy
λ2
LGk(x∗
1, x∗
2)


≥λ2
LGk(x1, x∗
2)


,
λ2
LGk(x∗
1, x∗
2)


≥λ2
LGk(x∗
1, x2)


,
for ∀x1 ∈X1 and ∀x2 ∈X2, where k denotes the time step,
and x = (x1, x2) is defined in Section III-A.
Note that at the NE point, no player can individually
increase the global network connectivity by reconfiguring
their robotic network, and the two-level MRN possesses an
equilibrium configuration.
V. SEMIDEFINITE PROGRAMMING AND ITERATIVE
ALGORITHM
In this section, we first derive a semidefinite programming
(SDP) approach to address the discretized optimization prob-
lems eQk
1 and eQk
2, and then design an iterative algorithm to
find the NE solution to the formulated MRN formation game.
A. Semidefinite Programming Formulation
Notice that in eQk
1 and eQk
2, the minimum distance constraints
||xij(k + 1)||2
2 ≥d1, ∀i, j ∈V1, and ||xij(k + 1)||2
2 ≥
d2, ∀i, j ∈V2, are nonconvex. To address this issue, one
method is to regard the distance ||xij(k+1)||2
2 = Zij(k+1) as
a new variable, and solve problems eQk
1 and eQk
2 with respect
to unknowns Zij(k + 1) and x(k + 1) jointly. In this way,
eQk
1 and eQk
2 become convex problems. However, due to the
coupling between the robots position and the distance vectors,
solving eQk
1 and eQk
2 via merely adding new variables will
yield inconsistency between the obtained solutions x(k + 1)
and Zij(k + 1), ∀i, j ∈V . Therefore, further considerations
are needed, and we first present the definition of Euclidean
distance matrix as follows.
Definition 2 (Euclidean Distance Matrix). Given the positions
of a set of n points denoted by N
:= {x1, ..., xn}, the
5
Euclidean distance matrix representing the points spacing is
defined as
D := [dij]i,j∈N ,
dij = ||xi −xj||2
2.
A critical property of the Euclidean distance matrix is
summarized in the following theorem.
Theorem 2 ([20]). A matrix D = [dij]i,j=1,...,n is an Eu-
clidean distance matrix if and only if
−CDC ⪰0, and dii = 0, i = 1, ..., n,
(14)
where C := In −1
n11T .
Note that (14) is a necessary and sufficient condition that
ensures D an Euclidean distance matrix. In addition, the
inequality and equality in (14) are both convex. Therefore,
Theorem 2 provides an approach to avoid the inconsistency
between the robots position and distance vectors when they
are treated as independent variables. In specific, denote Z =
[Zij]i,j∈V , C = In −1
n11T , and we can further reformulate
problems eQk
1 and eQk
2 as
Q
k
1 :
max
x1(k+1), Z(k+1), α1(k+1)
α1(k + 1)
s.t.
LG(k + 1) ⪰α1(k + 1)C,
2{xi(k + 1) −xj(k + 1)}T {xi(k) −xj(k)}
= Zij(k + 1) + Zij(k),
Zij(k + 1) ≥d1,
∀i, j ∈V1,
−CZ(k + 1)C ⪰0, Zii(k + 1) = 0, i ∈V,
xj(k + 1) = xj(k),
∀j ∈V2,
(15)
Q
k
2 :
max
x2(k+1), Z(k+1), α2(k+1)
α2(k + 1)
s.t.
LG(k + 1) ⪰α2(k + 1)C,
2{xi(k + 1) −xj(k + 1)}T {xi(k) −xj(k)}
= Zij(k + 1) + Zij(k),
Zij(k + 1) ≥d2,
∀i, j ∈V2,
−CZ(k + 1)C ⪰0, Zii(k + 1) = 0, i ∈V,
xj(k + 1) = xj(k),
∀j ∈V1.
(16)
Hence, Q
k
1 and Q
k
2 become convex and are semidefinite
programming problems which can be solved efficiently.
B. Iterative Algorithm
After obtaining the SDP problems Q
k
1 and Q
k
2, we aim
to find the solution that results in an equilibrium network
configuration. In the network formation game, P1 controls
robots in G1 and reconfigures the network by solving the
optimization problem Q
k
1 to obtain a new position of each
robot. P2 controls robots in network G2 in a similar way by
solving Q
k
2. Note that the players’ action at the current step can
be seen as a best-response to the network at the previous step.
Besides, the update frequency of each player in the discrete
time measure is needed to be determined. For given τ1 and
τ2 in the continuous time space, we can obtain their update
frequencies by normalizing them into integers denoted by s1
and s2, respectively. Then, P1 and P2 reconfigure their robots
for every s1 and s2 time intervals which can also be interpreted
as the frequency of solving Q
k
1 and Q
k
2, respectively. Since
both players maximize the global network connectivity at
every update step, then one approach to find the equilibrium
solution is to address Q
k
1 and Q
k
2 iteratively by two players
until the yielding MRN possesses the same topology, i.e.,
P1 and P2 cannot increase the network connectivity further
through relocating their robots.
C. Feasibility and Convergence
Before solving the problems Q
k
1 and Q
k
2, we should first
analyze their feasibility, and we have the following lemma.
Lemma 1. For a given initial multi-level MRN where the
distance between robots satisfies the predefined minimum
distance constraint, then the game problems Q
k
1 and Q
k
2 are
always feasible.
When Q
k
1 and Q
k
2 are feasible at each update step, another
essential property is the convergence of the proposed iterative
algorithm. Without loss of generality, we assume that two
players will not update at the same step which can be easily
achieved by normalizing the update frequency and choosing
the initial update step of two players appropriately. Then, the
convergence result is summarized in Theorem 3.
Theorem 3. The iterative algorithm converges to a Nash
equilibrium point asymptotically.
Proof: First, remind that both Q
k
1 and Q
k
2 maximize the
algebraic connectivity of the global network, and thus the
resulting αi(k+1), i ∈{1, 2}, is no less than the one obtained
from the previous update step which yields a non-decreasing
network connectivity sequence λ2. In addition, for a network
with n nodes, its algebraic connectivity is upper bounded
by n −1, [21]. Thus, based on the monotone convergence
theorem [22], we can conclude that the network connectivity
sequence converges asymptotically. Denote the actions of two
players that achieve the network connectivity limit as ¯x1 and
¯x2 at some step l, and then, we obtain λ2
LGl(¯x1, ¯x2)


≥
λ2
LGl(x1, ¯x2)


, λ2
LGl(¯x1, ¯x2)


≥λ2
LGl(¯x1, x2)


, for
∀x1 ∈X1 and ∀x2 ∈X2. Otherwise, ¯x1 and ¯x2 do not
result in the network connectivity limit. Obviously, the strategy
pair (¯x1, ¯x2) satisfies the NE Definition 1 which indicates
that the proposed iterative algorithm converges to a NE point
asymptotically.
Remark 4: A typical example of the iterative algorithm is
called alternating update in which P1 and P2 have the same
update frequency and reconfigure the MRN sequentially.
VI. ADVERSARIAL ATTACKS IN THE NETWORKS
Robots in the mobile networks are prone to malicious
attacks [8, 9, 23, 24]. Thus, their secure and resilient control is
essential. In this section, we first present three main types of
adversarial attacks to the mobile network including the global
positioning system (GPS) spoofing attack, targeted jamming
attack and denial-of-service (DoS) attack, and then analyze
their impacts on the network performance.
6
A. GPS Spoofing Attack
A GPS spoofing attack aims to deceive a GPS receiver in
terms of the object’s position, velocity and time by generating
counterfeit GPS signals [25]. In [7], the authors have demon-
strated that UAVs can be controlled by the attackers and go
to a wrong position through the GPS spoofing attack. In our
MRN, we consider the scenario that the physical movement
of a robot is constrained due to the attacks which can be
realized by adding a disruptive position signal to the robot’s
real control command. Therefore, through the GPS spoofing
attack, the mobile robot cannot move but still maintains its
communications with other robots in the network. In addition,
we assume that the attack cannot last forever but for a period of
ga in the discrete time measure which is reasonable, since the
resource of an attacker is limited, and the abnormal/unexpected
behavior of the other unattacked robots resulting from the
spoofing attack can be detected by the network administrator.
In the MRN, if robot i is compromised by the spoofing
attacker at time step k1, and the attack lasts for ga time steps,
then this scenario can be captured by adding the following
constraint to the problems Q
k
1 and Q
k
2:
xi(k + 1) = xi(k),
k = k1, ..., k1 + ga −1.
(17)
The attacked robot is usually randomly chosen. To evaluate
the impact of the attack, we choose the robot that has the
maximum degree which is denoted by imax. Then, we obtain
imax ∈arg max
i
X
j∈Ni
wij,
where Ni is the set of nodes that are connected to node i.
B. Targeted Jamming Attack
In wireless communication networks, one class of adver-
sarial event is the jamming attack which can be launched by
the attackers through injecting a huge amount of false data
into the communication links [9, 10]. In this attack scenario,
we consider the targeted jamming attack which means that
the attacker jams a certain wireless communication channel
between mobile robots which leads to a consequence of link
removal in the network.
To model this attack, denote the network as eG(i, j) =
(V, E \ (i, j)) after removing a link (i, j) ∈E from network
G, then, we have eL = L −∆L and ∆L = ∆D −∆A, where
∆D and ∆A are the decreased degree and adjacency matrices,
respectively. By using equation (1), we obtain ∆D and ∆A as
follows:
∆D = ei˜eT
i,j + ej˜eT
j,i,
∆A = ei˜eT
j,i + ej˜eT
i,j,
(18)
where ei and ˜ei,j are zero vectors except the i-th element
equaling to 1 and wij, respectively, and similar for ej and
˜ej,i. Denote the Laplacian matrix of eG(i, j) as eL(i, j), and by
using equations in (18), we have
eL(i, j) = L −
ei −ej

˜ei,j −˜ej,i

T .
(19)
Similar to the GPS spoofing attack, the targeted jamming
attack lasts for gb time steps. In order to incorporate this attack
into the mobile robotic networks model, we add the following
constraint to the Laplacian matrix:
wij(k) = 0,
k = k2, ..., k2 + gb −1,
(20)
where (i, j) denotes the attacked link, and k2 is the starting
point of the attack.
Attackers are often rational, i.e., they intentionally attack
those communication links that whose removal will lead to the
most decrease of the network connectivity. To characterize the
worst-case of targeted jamming attack, we have the following
analysis. When link (i, j) is attacked, the resulting Laplacian
is given by (19). Denote the Fiedler vector of L as u, and thus
uT Lu = λ2(L) based on the definition. By using (7), we can
obtain the following:
λ2
eL(i, j)


≤uT eL(i, j)u
= uT L −
ei −ej

˜ei,j −˜ej,i

T 

u
= uT Lu −(ui −uj)(wijui −wjiuj)
= λ2(L) −wij(ui −uj)2.
(21)
Therefore, by removing the link (i, j)∗, where
(i, j)∗∈arg max
(i,j)∈E wij(ui −uj)2,
(22)
the upper bound for λ2
eL(i, j)


is the smallest, and the
algebraic connectivity of G decreases the most.
C. Denial-of-Service Attack
In addition to the targeted link removal attack, another
attack scenario corresponding to the wireless communications
is the DoS attack [26]. The DoS attack can be realized by a
number of technical methods including Wormhole, Blackhole
and Grayhole attacks [27]. Specifically, in the MRN, the
malicious attacker generates false message to flood the robots’
communication resources which result in the node removal of
the network. When a node i ∈V is removed from the network
G, then all links that are connected to node i should also be
removed. Denote the Laplacian matrix of the network after the
attack as eL(i), and remind that Ni is the set of nodes that are
connected to node i. Then, similar to the analysis of the link
removal, we have
eL(i) = L −
X
j∈Ni
ei −ej

˜ei,j −˜ej,i

T .
(23)
If robot i is attacked at time k3, and the attack lasts for gc time
steps, then, the following constraint is added to the Laplacian
matrix:
wij(k) = 0,
∀j ∈V1 ∪V2, k = k3, ..., k3 + gc −1.
(24)
In addition, the worst-case of denial-of-service attack can be
captured as follows. When robot i is attacked, the Laplacian
of G is changed to (23). Similar to the analysis of the most
7
severe link removal attack, we obtain the following:
λ2
eL(i)


≤uT eL(i)u
= uT L −
X
j∈Ni
ei −ej

˜ei,j −˜ej,i

T 

u
= uT Lu −
X
j∈Ni
(ui −uj)(wijui −wjiuj)
= λ2(L) −
X
j∈Ni
wij(ui −uj)2.
(25)
Hence, by attacking robot i∗, where
i∗∈arg max
i
X
j∈Ni
wij(ui −uj)2,
(26)
the algebraic connectivity of G encounters the most decrease.
Remark 5: Depending on the scope of knowledge that the
attacker has of the network, our proposed game framework
can be used for attackers of different knowledge levels. For
example, an attacker may know the information of the whole
multi-level network or merely one sub-network. For the for-
mer case of attack, closed form solutions have already been
presented above. The analysis for the latter case can be done
in a similar way by focusing on a smaller network space.
VII. CASE STUDIES
In this section, we validate the obtained results via case
studies. Specifically, we first show the performance of the
two-level MRN by using the iterative algorithm. Then, we
further quantify the impact of malicious attacks introduced in
Section VI, and assess the resiliency and interdependency of
the network to malicious attacks.
A. Effectiveness of the Algorithm
In the case studies, both networks G1 and G2 include 6
mobile robots, and the minimum distance is set to 0.4. The
link strength parameters of inter-links in two networks are the
same, i.e., ρ1 = 1, ρ2 = 3 and α = 5, and for intra-links,
the parameters are equal to ρ1 = 1.5, ρ2 = 5 and α = 4.
Without loss of generality, P1 and P2 have the same update
frequency and they reconfigure their robotic networks in an
alternating fashion. In addition, YALMIP is adopted to solve
the corresponding SDP problems [28]. The obtained results
of the MRN configuration trajectory without attack and its
corresponding network algebraic connectivity are shown in
Fig. 2(a) and Fig. 2(b), respectively. In specific, the MRN
attains an equilibrium state after 10 updates which validates
the effectiveness of the iterative algorithm.
B. Impact of Malicious Attacks
In this section, we quantify the impact of each worst-case
attack introduced in Section VI on the network performance.
For clarity, we assume that each attack is launched at step
6 during the network formation game, and without loss of
generality, all attacks last for two steps. The result of network
algebraic connectivity under each attack condition is shown
in Fig. 3(a). We can see that the denial-of-service attack leads
to the most decrease of the network connectivity comparing
with other attacks, while the GPS spoofing attack is the least
severe one.
0
1
2
3
4
−1
−0.5
0
0.5
1
0
0.2
0.4
0.6
0.8
1
 1
 2
 3
 4
 5
 6
z
 7
 8
 9
10
11
12
x
y
initial position in G1
initial position in G2
intermidiate position
final position in G1
final position in G2
update trajectory
(a)
0
2
4
6
8
10
12
0
1
2
3
4
5
6
7
8
9
step
algebraic connectivity
(b)
Fig. 2.
(a) Configuration of a two-layer MRN without attack. (b) The
resulting algebraic connectivity of the network formation game without attack.
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
9
step
algebraic connectivity
GPS spoofing attack
Targeted jamming attack
Denial−of−service attack
Without attack
(a)
0
2
4
6
8
10
12
14
16
18
20
0
1
2
3
4
5
6
7
8
9
step
algebraic connectivity
GPS spoofing attack
Targeted jamming attack
Denial−of−service attack
Without attack
(b)
Fig. 3.
(a) The impact of each worst-case attack on the network connectivity.
(b) The algebraic connectivity of the network formation game without attack
and under each attack condition. Under the adversarial environment, the worst-
case attack happens at step 10, and it remains the same afterwards.
C. Resiliency of the Network to Attacks
After obtaining the impact of attacks on the network alge-
braic connectivity, the next step is to quantify the resiliency
of the MRN to attacks. In specific, the resiliency metric is
based on the system recovery speed and the recovery ability
under the adversarial attacks. The adopted MRN model is
the same as that in Section VII-A. In addition, we assume
that the attacks are added to the MRN at step 10, and the
attacker’s action remains the same in the following steps. Fig.
3(b) shows the corresponding results. Specifically, the GPS
spoofing attack does not impact the network performance in
this case, since the attack is added at the point where MRN is
of an equilibrium configuration, and the constrained physical
movement of robots is not sufficient to decrease the network
connectivity. For other cases, we can see that the MRN begins
to recover after the attack happens which shows the high-level
situational awareness of the MRN. Moreover, besides the GPS
spoofing attack, the MRN is the most resilient to the targeted
jamming attack by using the designed iterative algorithm in
terms of the agile recovery to a satisfying performance. The
DoS attack can cause a huge loss of the algebraic connectivity,
and the MRN cannot fully recover under this attack due to the
removal of a robot. However, the rate of the network reaching
a new NE is fast in this case.
D. Interdependency of Multi-level Robotic Networks
Comparing with single-level networks, a unique feature of
the multi-level networks is their inherent interdependencies.
We aim to show the existence of interdependency in the multi-
level MRN in this section. Fig. 4 depicts the evolution of
8
0.5
1
1.5
2
2.5
3
3.5
4
−1
−0.5
0
0.5
1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
 1
 2
 3
 4
 5
 6
z
 7
 8
 9
10
11
12
y
x
initial position in G1
initial position in G2
intermidiate position
position in G1 before attack
position in G2 before attack
position in G1 after attack
position in G2 after attack
update trajectory
attacked robot
Fig. 4.
MRN configuration under the DoS attack. The attack is introduced
at step 10 where the initial network formation game reaches an equilibrium.
Both mobile networks will respond to the DoS attack in the following update
steps until reaching another equilibrium.
mobile network configuration corresponding to the DoS attack
scenario in Section VII-C. Remind that the attack happens
at time step 10 where the network is under an equilibrium
state. After introducing the attack, the two levels of robots
will respond to it by moving to a new position, validating
the resiliency of MRN. In addition, by comparing two robotic
networks in Fig. 2(a) and Fig. 4, we find that robots in the
network without attack (upper level) will move toward a posi-
tion that can allow to set up the most intra-links with robots in
the attacked network (lower level), and this fact corroborates
the natural interdependency between two networks. Due to
the interdependency, the whole mobile network can be more
resilient to malicious attacks.
VIII. CONCLUSION
In this paper, we have investigated the connectivity control
of multi-level mobile robotic networks. We have developed
a decentralized resilient algorithm to maximize the algebraic
connectivity of the network to adversarial attacks, and shown
its asymptotic convergence to a Nash equilibrium. Three types
of attack models have been introduced, and their impacts
have been quantified. Moreover, case studies have shown
that the GPS spoofing attack has the least impact on the
network performance, and the robotic network is the most
resilient to the targeted jamming attack than other attacks
by using the proposed control method. Future work can be
designing a model predictive control algorithm that enables
robots connectivity-aware during the network formation game.
REFERENCES
[1] N. Michael, M. M. Zavlanos, V. Kumar, and G. J. Pappas,
“Maintaining connectivity in mobile robot networks,” in
Experimental Robotics.
Springer, 2009, pp. 117–126.
[2] Y. Kim and M. Mesbahi, “On maximizing the second
smallest eigenvalue of a state-dependent graph laplacian,”
IEEE Transactions on Automatic Control, vol. 51, no. 1,
pp. 116–120, 2006.
[3] A. Simonetto, T. Keviczky, and R. Babuska, “On dis-
tributed maximization of algebraic connectivity in robotic
networks,” in American Control Conference, 2011, 2011,
pp. 2180–2185.
[4] G. D’Agostino and A. Scala, Networks of networks: the
last frontier of complexity.
Springer, 2014, vol. 340.
[5] J. Mart´ın-Hern´andez, H. Wang, P. Van Mieghem, and
G. DAgostino, “Algebraic connectivity of interdependent
networks,” Physica A: Statistical Mechanics and its Ap-
plications, vol. 404, pp. 92–105, 2014.
[6] U. Zengin and A. Dogan, “Real-time target tracking for
autonomous uavs in adversarial environments: a gradi-
ent search algorithm,” IEEE Transactions on Robotics,
vol. 23, no. 2, pp. 294–307, 2007.
[7] A. J. Kerns, D. P. Shepard, J. A. Bhatti, and T. E.
Humphreys, “Unmanned aircraft capture and control via
gps spoofing,” Journal of Field Robotics, vol. 31, no. 4,
pp. 617–636, 2014.
[8] 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.
[9] C. Karlof and D. Wagner, “Secure routing in wireless
sensor networks: Attacks and countermeasures,” Ad hoc
networks, vol. 1, no. 2, pp. 293–315, 2003.
[10] Q. Zhu, W. Saad, Z. Han, H. V. Poor, and T. Bas¸ar,
“Eavesdropping and jamming in next-generation wireless
networks: A game-theoretic approach,” in IEEE Military
Communications Conference, 2011, pp. 119–124.
[11] A. Ghosh and S. Boyd, “Growing well-connected
graphs,” in IEEE Conference on Decision and Control,
2006, pp. 6605–6611.
[12] R. Dai and M. Mesbahi, “Optimal topology design for
dynamic networks,” in IEEE Conference on Decision and
Control and European Control Conference, 2011, pp.
1280–1285.
[13] L. Sabattini, N. Chopra, and C. Secchi, “Decentralized
connectivity maintenance for cooperative control of mo-
bile robotic systems,” International Journal of Robotics
Research, vol. 32, no. 12, pp. 1411–1423, 2013.
[14] M. M. Zavlanos and G. J. Pappas, “Distributed connec-
tivity control of mobile networks,” IEEE Transactions on
Robotics, vol. 24, no. 6, pp. 1416–1428, 2008.
[15] M.
Fiedler,
“Algebraic
connectivity
of
graphs,”
Czechoslovak Mathematical Journal, vol. 23, no. 2, pp.
298–305, 1973.
[16] D. Tse and P. Viswanath, Fundamentals of wireless
communication.
Cambridge university press, 2005.
[17] D. Monderer and L. S. Shapley, “Potential games,”
Games and economic behavior, vol. 14, no. 1, pp. 124–
143, 1996.
[18] R. A. Horn and C. R. Johnson, Matrix analysis.
Cam-
bridge university press, 2012.
[19] H. Nagarajan, S. Rathinam, S. Darbha, and K. Rajagopal,
“Algorithms for synthesizing mechanical systems with
maximal natural frequencies,” Nonlinear Analysis: Real
World Applications, vol. 13, no. 5, pp. 2154–2162, 2012.
[20] J. Dattorro, Convex optimization & Euclidean distance
geometry.
Meboo Publishing, 2008.
[21] C. Godsil and G. F. Royle, Algebraic graph theory.
Springer Science & Business Media, 2013, vol. 207.
[22] B. Ganter and R. Wille, Formal concept analysis: math-
ematical foundations.
Springer Science & Business
9
Media, 2012.
[23] F.-H. Tseng, L.-D. Chou, and H.-C. Chao, “A survey of
black hole attacks in wireless mobile ad hoc networks,”
Human-centric Computing and Information Sciences,
vol. 1, no. 1, pp. 1–16, 2011.
[24] R. H. Khokhar, M. A. Ngadi, and S. Mandala, “A review
of current routing attacks in mobile ad hoc networks,”
International Journal of Computer Science and Security,
vol. 2, no. 3, pp. 18–29, 2008.
[25] D. M. Akos, “Who’s afraid of the spoofer? gps/gnss
spoofing detection via automatic gain control (agc),”
Navigation, vol. 59, no. 4, pp. 281–290, 2012.
[26] A. D. Wood and J. A. Stankovic, “Denial of service in
sensor networks,” Computer, vol. 35, no. 10, pp. 54–62,
2002.
[27] R. H. Jhaveri, S. J. Patel, and D. C. Jinwala, “DoS
attacks in mobile ad hoc networks: A survey,” in IEEE
International Conference on Advanced Computing &
Communication Technologies, 2012, pp. 535–541.
[28] J. Lofberg, “YALMIP: A toolbox for modeling and op-
timization in matlab,” in IEEE International Symposium
on Computer Aided Control Systems Design, 2004, pp.
284–289.