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. I NTRODUCTION  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  G 1  G 2  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. B ACKGROUND AND   I NTERDEPENDENT  N ETWORK   M ODEL  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   w ij   , we define two vectors   a e   ∈   R n  and   b e   ∈   R n , where   a e ( i ) = 1 ,   a e ( j ) =   − 1 ,   b e ( i ) =   w ij   ,  b e ( j ) =   − w ij   , and other entries 0. Then, the Laplacian matrix  L   of network   G   can be expressed as  L   =  m ∑  e =1  a e b T e   .   (1) Basically, for the weighted Laplacian matrix   L , its diagonal entries are equal to   L ii   =   ∑  j ∈ N i   w ij   ,   ∀ i   ∈   V   , where   N i  denotes the set of nodes that are connected to node   i . In addition,   L ij   =   − w ij   if nodes   i   and   j   are connected, for  i   6   =   j   ∈   V   , and 0 otherwise. Note that   w ij   =   w ji ,   ∀ 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   G 1 ( V 1 , E 1 )   and   G 2 ( V 2 , E 2 ) , where network 1 and network 2 are represented by   G i , for   i   = 1 ,   2 , respectively. Network   i ,   i   ∈   { 1 ,   2 } , is composed of   n i   =   | V i |   nodes and   m i   =   | E i |   links. The global network resulting from the connection of these two networks can be represented by  G   = ( V 1   ∪   V 2 ,   E 1   ∪   E 2   ∪   E 12 ) , where   E 12   is a set of  intra-links   between   G 1   and   G 2 . For convenience, we denote the network consisting of the intra-links between   G 1   and   G 2  as   G 12 . The adjacency matrix   A   of the global network   G   has the entry  a ij   =  {   w ij   ,   nodes   i   and   j   are connected; 0 ,   nodes   i   and   j   are not connected .  Let   A 1   ∈   R n 1 × n 1   and   A 2   ∈   R n 2   × n 2   be the adjacency matrices of   G 1   and   G 2 , respectively, and   n   =   n 1   +   n 2 . When   E 12   6   =   ∅ , the adjacency matrix   A   ∈   R n × n   takes the following form  A   =  [   A 1   B 12  B T  12   A 2  ]  ,  where   B 12   ∈   R n 1   × n 2   is a matrix used to capture the effect of intra-links between networks. Define two diagonal matrices  D 1   ∈   R n 1   × n 1   and   D 2   ∈   R n 2 × n 2   as  ( D 1 ) ii   =   ∑  j  ( B 12 ) ij   ,   ( D 2 ) ii   =   ∑  j  ( B T  12 ) ij   .  Then, by using   L   =   D   −   A ,   we obtain the Laplacian matrix  L   =  [ L 1   +   D 1   − B 12  − B T  12   L 2   +   D 2  ]  ,   (3) where   L 1   and   L 2   are the Laplacians corresponding to   A 1   and  A 2 , respectively.  Remark 1 :   The above formulated two-layer interdependent framework can be easily extended to multi-layer cases. III. P ROBLEM   F ORMULATION  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 ) =   ( x 1 ( t ) , x 2 ( t ) , ..., x n ( t ) )   ∈   R 3 × n , and the dynamic of each robot   i   is given by    ̇ x i ( t ) =   u i ( t ) ,   where   u i ( t )   ∈   R 3   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   :   R 3   ×   R 3   →   R +   to each communication link   ( i, j ) , such that  w ij   ( t ) =   w ( x i ( t ) , x j   ( t ) )   =   g ( ‖   x ij   ( t )   ‖ 2 ) ,  for some   g   :   R +   →   R + , where   x ij   ( t ) :=   x i ( t )   −   x j   ( t ) . The strength of a communication link decays exponentially with the distance [16]. Therefore, the entries   A ij   of the adjacency matrix   A   admit  A ij   =          1 ,   ‖   x ij   ( t )   ‖ 2 < ρ 1 ;  e   − α ( ‖ xij   ( t ) ‖ 2   − ρ 1)  ρ 2   − ρ 1   ,   ρ 1   ≤‖   x ij   ( t )   ‖ 2 ≤   ρ 2 ; 0 ,   ‖   x ij   ( 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   G 1 , and robots in the bottom layer belong to network   G 2 . For convenience, we label robots in   G 1   as   1 ,   2 , ..., n 1   ∈   V 1 , and robots in   G 2  as   n 1   + 1 , n 1   + 2 , ..., n 1   +   n 2   ∈   V 2 . 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   G 1   and   G 2 , 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 ( P 1 ) and player 2 ( P 2 ), play a network formation game.   P 1   controls robots in network   G 1 , and   P 2   controls robots in   G 2 . Specifically,  P 1   and   P 2   update their own mobile network iteratively by controlling the robots’ positions which are denoted as   x 1  and   x 2 , respectively. Note that   x 1   := ( x 1 , ..., x n 1   )   ∈   R 3 × n 1   ,  x 2   := ( x n 1   +1 , ..., x n )   ∈   R 3 × n 2   , and   x   := ( x 1 ,   x 2 ) . 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  ( L G ( x ) ) , at every step. In addition, the action spaces of   P 1   and   P 2   are denoted by   X 1   and   X 2 , respectively, which include all the possible network configurations. The set of pure strategy profiles   X   :=   X 1   ×   X 2   is the Cartesian product of the individual pure strategy sets. Besides, the utility function for both players is   λ 2  ( L G ( 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   G 1   and   G 2   denoted by  d 1   and   d 2 , respectively. Then, the network formation game can be represented by two individual   interdependent   optimization problems   Q t  1   and   Q t  2   as follows:  Q t  1   :   max  x 1 ( t + τ 1 )   λ 2  ( L G ( x ( t   +   τ 1 )) )  s . t .   || x ij   ( t   +   τ 1 ) || 2 2   ≥   d 1 ,   ∀ i, j   ∈   V 1 , x j   ( t   +   τ 1 ) =   x j   ( t ) ,   ∀ j   ∈   V 2 .  (5)  Q t  2   :   max  x 2 ( t + τ 2 )   λ 2  ( L G ( x ( t   +   τ 2 )) )  s . t .   || x ij   ( t   +   τ 2 ) || 2 2   ≥   d 2 ,   ∀ i, j   ∈   V 2 , x j   ( t   +   τ 2 ) =   x j   ( t ) ,   ∀ j   ∈   V 1 ,  (6) where   V 1   and   V 2   denote the sets of nodes in   G 1   and   G 2 , 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   Q t  1   and  Q t  2   can be characterized as a constrained   potential game   due to the identical objective of two players [17]. IV. S YSTEM   D YNAMICS   D ISCRETIZATION AND  E QUILIBRIUM   S OLUTION   C ONCEPT  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 ( L G ( x )) =   min  || z || 2 =1 ,z ⊥ 1   z T   L G ( 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 ( L G ( x ))   is concave in   L G ( x ) . Therefore, the ACMP  max x   λ 2 ( L G ( 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   max x   λ 2 ( L G ( x ))   is equivalent to the follow- ing:  max  x , α   α  s . t .   L G ( x )      α   ·   ( I n   −   1  n   11 T   ) ,  (8)  where   α   ∈   R , and   I n   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   Q t  1   and   Q t  2   in the following. First, we deal with the minimum distance constraint. By denoting
4  Z ij   ( t ) =   || x ij   ( t ) || 2 2 , and then differentiating   || x ij   ( t ) || 2 2   with respect to the time, we obtain [2]  2 {    ̇ x i ( t )   −    ̇ x j   ( t ) } T   { x i ( t )   −   x j   ( t ) }   =    ̇ Z ij   ( 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 { x i ( k   + 1)   −   x j   ( k   + 1) } T   { x i ( k )   −   x j   ( k ) }  =   Z ij   ( k   + 1)+ Z ij   ( k ) .   (10) Similarly, differentiating and discretizing weight   w ij   yield  w ij   ( k   + 1) =   w ij   ( k ) +   ∂f   ( || x ij   || 2 )  ∂ || x ij   || 2  ∣ ∣ ∣ ∣ k  { x ij   ( k   + 1)   −   x ij   ( k ) } .  (11) Hence, we can obtain a discrete Laplacian matrix   L G  ( 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  x 2 ( k )   and   x 1 ( k )   for   P 1   and   P 2 , respectively, we can reformu- late the problems   Q t  1   and   Q t  2   as follows:   ̃ Q k  1   :   max  x 1 ( k +1) , α 1 ( k +1)   α 1 ( k   + 1) s . t .   L G ( k   + 1)      α 1 ( k   + 1)   ·   ( I n   −   1  n   11 T   ) ,  2 { x i ( k   + 1)   −   x j   ( k   + 1) } T   { x i ( k )   −   x j   ( k ) }  =   Z ij   ( k   + 1) +   Z ij   ( k ) ,  || x ij   ( k   + 1) || 2 2   ≥   d 1 ,   ∀ i, j   ∈   V 1 , x j   ( k   + 1) =   x j   ( k ) ,   ∀ j   ∈   V 2 ,  (12)   ̃ Q k  2   :   max  x 2 ( k +1) , α 2 ( k +1)   α 2 ( k   + 1) s . t .   L G ( k   + 1)      α 2 ( k   + 1)   ·   ( I n   −   1  n   11 T   ) ,  2 { x i ( k   + 1)   −   x j   ( k   + 1) } T   { x i ( k )   −   x j   ( k ) }  =   Z ij   ( k   + 1) +   Z ij   ( k ) ,  || x ij   ( k   + 1) || 2 2   ≥   d 2 ,   ∀ i, j   ∈   V 2 , x j   ( k   + 1) =   x j   ( k ) ,   ∀ j   ∈   V 1 ,  (13) where   α 1 ( k   + 1)   and   α 2 ( k   + 1)   are the scalar objectives of   ̃ Q k  1   and    ̃ Q k  2   , respectively. In addition, we obtain the discrete Laplacian matrix   L G ( k   + 1)   by using (11), and its entries   l G ij   ( k   + 1)   are  l G ij   ( k   + 1) =                    −   w ij   ( k   + 1) ,   if   i   6   =   j,   ( i, j )   ∈   E 1   ∪   E 2 ;  −    ̃ w ij   ( k   + 1) ,   if   i   ∈   V 1 , j   ∈   V 2 ,   or   j   ∈   V 1 , i   ∈   V 2 ;  ∑  s 6 = i,s ∈ V 1  w is ( k   + 1) +   ∑  q 6   = i,q ∈ V 2   ̃ w iq   ( k   + 1) ,   if   i   =   j   ∈   V 1 ;  ∑  s 6 = i,s ∈ V 2  w is ( k   + 1) +   ∑  q 6   = i,q ∈ V 1   ̃ w iq   ( k   + 1) ,   if   i   =   j   ∈   V 2 ;  where   w ij   ,   ∀ ( i, j )   ∈   E 1   ∪   E 2 ,   represent the weight of interlinks inside   G 1   and   G 2 , and    ̃ w ij   ,   ∀ ( i, j )   ∈   E 12 , denote the weight of intra-links connecting   G 1   and   G 2 .  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   P 1   takes his action at step   k ,   G 1   and  G 12   are reconfigured, where   G 12   is the network between  G 1   and   G 2 . We denote network   G 1   and   G 12   at stage   k   as  G 1 ,k   and   G 12 ,k , respectively. For simplicity, we further define   ̃ G 12 ,k   :=   G 1 ,k   ∪   G 12 ,k , which is a shorthand notation for the merged network. Then, network   G k   can be expressed as  G k   =    ̃ G 12 ,k   ∪ G 2 ,k . Similarly, after   P 2   updates network   G 2   at step   k , the whole network   G k   becomes   G k   =    ̃ G 21 ,k   ∪   G 1 ,k , where    ̃ G 21 ,k   :=   G 2 ,k   ∪   G 12 ,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  ( L G k   ( x ∗  1   ,   x ∗  2 ) )   ≥   λ 2  ( L G k   ( x 1 ,   x ∗  2 ) ) , λ 2  ( L G k   ( x ∗  1   ,   x ∗  2 ) )   ≥   λ 2  ( L G k   ( x ∗  1 ,   x 2 ) ) ,  for   ∀ x 1   ∈   X 1   and   ∀ x 2   ∈   X 2 , where   k   denotes the time step, and   x   = ( x 1 ,   x 2 )   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. S EMIDEFINITE   P ROGRAMMING AND   I TERATIVE  A LGORITHM  In this section, we first derive a semidefinite programming (SDP) approach to address the discretized optimization prob- lems    ̃ Q k  1   and    ̃ Q k  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    ̃ Q k  1   and    ̃ Q k  2   , the minimum distance constraints  || x ij   ( k   + 1) || 2 2   ≥   d 1 ,   ∀ i, j   ∈   V 1 , and   || x ij   ( k   + 1) || 2 2   ≥  d 2 ,   ∀ i, j   ∈   V 2 , are   nonconvex . To address this issue, one method is to regard the distance   || x ij   ( k +1) || 2 2   =   Z ij   ( k +1)   as a new variable, and solve problems    ̃ Q k  1   and    ̃ Q k  2   with respect to unknowns   Z ij   ( k   + 1)   and   x ( k   + 1)   jointly. In this way,   ̃ Q k  1   and    ̃ Q k  2   become convex problems. However, due to the coupling between the robots position and the distance vectors, solving    ̃ Q k  1   and    ̃ Q k  2   via merely adding new variables will yield inconsistency between the obtained solutions   x ( k   + 1)  and   Z ij   ( 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   :=   { x 1 , ..., x n } , the
5  Euclidean distance matrix representing the points spacing is defined as  D   := [ d ij   ] i,j ∈N   ,   d ij   =   || x i   −   x j   || 2 2 .  A critical property of the Euclidean distance matrix is summarized in the following theorem.  Theorem 2   ([20]) .   A matrix   D   = [ d ij   ] i,j =1 ,...,n   is an Eu- clidean distance matrix if and only if  −   CDC      0 ,   and   d ii   = 0 , i   = 1 , ..., n,   (14)  where   C   :=   I n   −   1  n   11 T   .  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   = [ Z ij   ] i,j ∈ V   ,   C   =   I n   −   1  n   11 T   , and we can further reformulate problems    ̃ Q k  1   and    ̃ Q k  2   as  Q k  1   :   max  x 1 ( k +1) ,   Z ( k +1) , α 1   ( k +1)   α 1 ( k   + 1) s . t .   L G ( k   + 1)      α 1 ( k   + 1) C ,  2 { x i ( k   + 1)   −   x j   ( k   + 1) } T   { x i ( k )   −   x j   ( k ) }  =   Z ij   ( k   + 1) +   Z ij   ( k ) ,  Z ij   ( k   + 1)   ≥   d 1 ,   ∀ i, j   ∈   V 1 ,  −   CZ ( k   + 1) C      0 ,   Z ii ( k   + 1) = 0 , i   ∈   V, x j   ( k   + 1) =   x j   ( k ) ,   ∀ j   ∈   V 2 ,  (15)  Q k  2   :   max  x 2 ( k +1) ,   Z ( k +1) , α 2   ( k +1)   α 2 ( k   + 1) s . t .   L G ( k   + 1)      α 2 ( k   + 1) C ,  2 { x i ( k   + 1)   −   x j   ( k   + 1) } T   { x i ( k )   −   x j   ( k ) }  =   Z ij   ( k   + 1) +   Z ij   ( k ) ,  Z ij   ( k   + 1)   ≥   d 2 ,   ∀ i, j   ∈   V 2 ,  −   CZ ( k   + 1) C      0 ,   Z ii ( k   + 1) = 0 , i   ∈   V, x j   ( k   + 1) =   x j   ( k ) ,   ∀ j   ∈   V 1 .  (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,   P 1   controls robots in   G 1   and reconfigures the network by solving the optimization problem   Q k  1   to obtain a new position of each robot.   P 2   controls robots in network   G 2   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   s 1  and   s 2 , respectively. Then,   P 1   and   P 2   reconfigure their robots for every   s 1   and   s 2   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.,  P 1   and   P 2   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    ̄ x 1   and   ̄ x 2   at some step   l , and then, we obtain   λ 2  ( L G l   ( ̄ x 1 ,    ̄ x 2 ) )   ≥  λ 2  ( L G l   ( x 1 ,    ̄ x 2 ) ) ,   λ 2  ( L G l   ( ̄ x 1 ,    ̄ x 2 ) )   ≥   λ 2  ( L G l   ( ̄ x 1 ,   x 2 ) ) ,   for  ∀ x 1   ∈   X 1   and   ∀ x 2   ∈   X 2 . Otherwise,    ̄ x 1   and    ̄ x 2   do not result in the network connectivity limit. Obviously, the strategy pair   ( ̄ x 1 ,    ̄ x 2 )   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   P 1   and   P 2   have the same update frequency and reconfigure the MRN sequentially. VI. A DVERSARIAL   A TTACKS IN THE   N ETWORKS  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  g a   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   k 1 , and the attack lasts for   g a   time steps, then this scenario can be captured by adding the following constraint to the problems   Q k  1   and   Q k  2   :  x i ( k   + 1) =   x i ( k ) ,   k   =   k 1 , ..., k 1   +   g a   −   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   i max . Then, we obtain  i max   ∈   arg max  i  ∑  j ∈ N i  w ij   ,  where   N i   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    ̃ G ( i, j )   = ( V, E   \   ( i, j ))   after removing a link   ( i, j )   ∈   E   from network  G , then, we have    ̃ L   =   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   =   e i  ̃ e T i,j   +   e j  ̃ e T j,i ,  ∆ A   =   e i  ̃ e T j,i   +   e j  ̃ e T i,j   ,   (18) where   e i   and    ̃ e i,j   are zero vectors except the   i -th element equaling to 1 and   w ij   , respectively, and similar for   e j   and   ̃ e j,i . Denote the Laplacian matrix of    ̃ G ( i, j )   as    ̃ L ( i, j ) , and by using equations in (18), we have   ̃ L ( i, j ) =   L   −   ( e i   −   e j  )(  ̃ e i,j   −    ̃ e j,i  ) T   .   (19) Similar to the GPS spoofing attack, the targeted jamming attack lasts for   g b   time steps. In order to incorporate this attack into the mobile robotic networks model, we add the following constraint to the Laplacian matrix:  w ij   ( k ) = 0 ,   k   =   k 2 , ..., k 2   +   g b   −   1 ,   (20) where   ( i, j )   denotes the attacked link, and   k 2   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  u T   Lu   =   λ 2 ( L )   based on the definition. By using (7), we can obtain the following:  λ 2  ( ̃ L ( i, j ) )   ≤   u T    ̃ L ( i, j ) u  =   u T   ( L   −   ( e i   −   e j  )(  ̃ e i,j   −    ̃ e j,i  ) T   ) u  =   u T   Lu   −   ( u i   −   u j   )( w ij   u i   −   w ji u j   ) =   λ 2 ( L )   −   w ij   ( u i   −   u j   ) 2 .  (21) Therefore, by removing the link   ( i, j ) ∗ , where  ( i, j ) ∗   ∈   arg max  ( i,j ) ∈ E   w ij   ( u i   −   u j   ) 2 ,   (22) the upper bound for   λ 2  ( ̃ L ( 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    ̃ L ( i ) , and remind that   N i   is the set of nodes that are connected to node   i . Then, similar to the analysis of the link removal, we have   ̃ L ( i ) =   L   −   ∑  j ∈ N i  ( e i   −   e j  )(  ̃ e i,j   −    ̃ e j,i  ) T   .   (23) If robot   i   is attacked at time   k 3 , and the attack lasts for   g c   time steps, then, the following constraint is added to the Laplacian matrix:  w ij   ( k ) = 0 ,   ∀ j   ∈   V 1   ∪   V 2 , k   =   k 3 , ..., k 3   +   g c   −   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  ( ̃ L ( i ) )   ≤   u T    ̃ L ( i ) u  =   u T   ( L   −   ∑  j ∈ N i  ( e i   −   e j  )(  ̃ e i,j   −    ̃ e j,i  ) T   ) u  =   u T   Lu   −   ∑  j ∈ N i  ( u i   −   u j   )( w ij   u i   −   w ji u j   ) =   λ 2 ( L )   −   ∑  j ∈ N i  w ij   ( u i   −   u j   ) 2 .  (25) Hence, by attacking robot   i ∗ , where  i ∗   ∈   arg max  i  ∑  j ∈ N i  w ij   ( u i   −   u j   ) 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. C ASE   S TUDIES  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   G 1   and   G 2   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,   P 1   and   P 2   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 G 1  initial position in G 2  intermidiate position  final position in G 1  final position in G 2  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 G 1  initial position in G 2  intermidiate position  position in G 1   before attack  position in G 2   before attack  position in G 1   after attack  position in G 2   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. C ONCLUSION  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. R EFERENCES  [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.