1

Dynamic Connectivity Game for Adversarial
Internet of Battlefield Things Systems

arXiv:1708.05741v2 [cs.IT] 22 Dec 2017

Nof Abuzainab and Walid Saad, Senior Member, IEEE,
Abstract—In this paper, the problem of network connectivity
is studied for an adversarial Internet of Battlefield Things (IoBT)
system in which an attacker aims at disrupting the connectivity
of the network by choosing to compromise one of the IoBT nodes
at each time epoch. To counter such attacks, an IoBT defender
attempts to reestablish the IoBT connectivity by either deploying
new IoBT nodes or by changing the roles of existing nodes. This
problem is formulated as a dynamic multistage Stackelberg connectivity game that extends classical connectivity games and that
explicitly takes into account the characteristics and requirements
of the IoBT network. In particular, the defender’s payoff captures
the IoBT latency as well as the sum of weights of disconnected
nodes at each stage of the game. Due to the dependence of the
attacker’s and defender’s actions at each stage of the game on the
network state, the feedback Stackelberg solution (FSE) is used
to solve the IoBT connectivity game. Then, sufficient conditions
under which the IoBT system will remain connected, when the
FSE solution is used, are determined analytically. Numerical
results show that the expected number of disconnected sensors,
when the FSE solution is used, decreases up to 46% compared to
a baseline scenario in which a Stackelberg game with no feedback
is used, and up to 43% compared to a baseline equal probability
policy.

I. I NTRODUCTION
HE Internet of Things (IoT) is expected to revolutionize the military battlefield in various aspects [1]–[3].
By interconnecting all military units, including soldiers and
vehicles, with various IoT devices, sensors, and actuators,
the IoT provides autonomy in the battlefield and increases
the efficiency of military networks. An IoT-enabled battlefield
will allow military commanders to acquire instanteneous information on the status of the military units. For instance,
wearables can provide instant updates on the situation of soldiers, and sensors mounted on vehicles can provide real-time
information on the status of each vehicle. Another important
IoT feature that makes it suitable for the battlefield is its
support for mobile crowdsensing. In mobile crowdsensing,
various IoT devices such as handheld devices, wearables,
vehicles, and sensors collaborate in sensing a particular type
of information. In traditional military networks, on the other
hand, dedicated sensors are deployed for each application.
Thus, a dense deployment of IoT devices can provide more

T

N. Abuzainab and W. Saad are with the department of Electrical and
Computer Engineering, Virginia Tech, Blacksburg, VA, USA, e-mail: {nof,
walids}@vt.edu
This research was sponsored by the Army Research Laboratory and was
accomplished under Grant Number W911NF-17-1-0021. The views and
conclusions contained in this document are those of the authors and should
not be interpreted as representing the official policies, either expressed or
implied, of the Army Research Laboratory or the U.S. Government. The U.S.
Government is authorized to reproduce and distribute reprints for Government
purposes notwithstanding any copyright notation herein.
Copyright (c) 2012 IEEE. Personal use of this material is permitted.
However, permission to use this material for any other purposes must be
obtained from the IEEE by sending a request to pubs-permissions@ieee.org.

accurate and detailed information about the battlefield, which
can, in turn, allow building comprehensive situation awareness
and enabling more accurate decision making. This imminent
integration of the IoT with military networks forms the nexus
of the so-called Internet of Battlefield Things (IoBT) [1].
Naturally, in an IoBT, connectivity is very critical for the
successful operation of the military network as it is essential
to maintain the autonomy of the system. Military missions,
such as surveillance and situational awareness, will heavily
rely on the information collected for the battlefield, and, thus,
any disconnection in the IoBT system will result in inaccurate
decision making and poor situational awareness. In fact, the
IoBT is more vulnerable than commercial IoT networks due to
the adversarial nature of the battlefield, in which the devices
are continuously subject to security attacks. Moreover, IoBT
devices are typically small and low-cost devices that do not
support strong security mechanisms, and, hence, they can
be easily compromised by adversaries. The vulnerability of
the IoBT devices necessitates the design of novel security
solutions that are robust to adversaries and that can maintain
the connectivity of the IoBT in adversarial settings.
Connectivity reconstruction solutions were initially designed for wireless networks such as in [4] in which the nodes
select their transmission powers to maintain network connectivity. In [5] and [6], connectivity establishment mechanisms
are proposed to reestablish connectivity between sensors that
were isolated, due to faults or attacks, and a central sink in a
sensor network. In [5], the connectivity problem is formulated
as a single leader, multiple followers Stackelberg game in
which a cloud acts as the leader and chooses to activate sleep
nodes in order to maintain full connectivity, whereas the sleep
nodes act as followers with each seeking to maximize the
number of isolated nodes that it reconnects to the network.
In [6], stochastic geometry is used to design a relay-based
connectivity recovery scheme for a wireless sensor network
whose the goal is to optimize the tradeoff between the number
of selected relays and the energy spent to restore connectivity.
In [7], the authors derive conditions for regional connectivity
in an IoT industrial system while optimizing sensor coverage.
The work In [8] proposes a dynamic clustering and routing algorithm to maintain connectivity and achieve energy efficiency
in a large scale sensor network. In [9], a dynamic mobileaware IoT topology control scheme, based on a potential
game, is proposed in order to optimize IoT connectivity. The
work in [10] introduces a resilience mechanism to maintain
percolation-based connectivity in an IoT network in which an
adversary seeks to attack highly connected IoT nodes in order
to achieve the maximum possible damage. In the model of
[10], the IoT nodes report a one bit estimate of their attack
status to a common fusion center. Then, the objective of the

2

fusion center is to choose the nodes to survey such that the
number of nodes with highest degree under attack is kept
below a required threshold. The problem is formulated as a
zero-sum game between the fusion center and the attacker. In
[11], a time-reversal scheme is proposed in an IoT network
to enable connectivity between devices with heterogeneous
bandwidth requirements.
However, most of these existing works [4]–[11] consider
the connectivity problem in conventional sensor networks in
which all the nodes are simple sensors of the same type
and capabilities, whereas in the IoBT, the nodes can have
heterogeneous roles and capabilities. In fact, each IoBT device
can possess multiple sensors each of which is collecting
different types of information. Thus, the importance of each
device is dependent on the number of types of information it
is sensing. Further, the IoBT will integrate high end nodes,
commonly known as sinks, that collect the different information from the IoBT devices and perform complex operations
in order to obtain useful information needed by the military
commanders [1]–[3]. Thus, the effect of disconnection on
the IoBT depends on the type of the node that gets isolated
from the network. Further, prior art such as in [4]–[11] does
not adequately capture the dynamics of interaction between
defenders and adversaries in a battlefield. Thus, there is a need
to introduce new dynamic connectivity solutions that consider
the heterogeneity of the IoBT nodes and dynamically adapt to
the actions of adversaries in the battlefield.
The main contributions of this paper are summarized next:
• We develop a novel adaptive framework for dynamically
optimizing the connectivity of an adversarial IoBT network. In particular, we consider the connectivity problem in an IoBT that includes a set of heterogeneous
devices that sense different types of information. The
IoBT devices must transmit their information, through
intermediary local sinks, to the general sink. We consider
an adversarial IoBT in which an attacker is interested
in causing disconnection to the network by choosing to
compromise one of the IoBT nodes at each time epoch.
Meanwhile, the IoBT operator acts as a defender that
strives to maintain the connectivity of the IoBT network
by either deploying new IoBT nodes or changing the
roles of the nodes. The objective of the attacker and the
defender is to maximize their sum of payoffs until the
end of the military operation.
• We formulate the connectivity problem in the IoBT
using the framework of connectivity games [12] which
are game-theoretic frameworks suitable for addressing
problems that involve the maintenance and restoration
of a network in presence of adversaries. However, in
classical connectivity games, the sole objective is to
restore or maintain the network connectivity, whereas in
the IoBT, there are other performance metrics that must
be considered such as the latency of communication.
Thus, we propose a novel IoBT connectivity game that
is tailored to the characteristics and requirements of the
IoBT. In particular, the attacker’s payoff is expressed as
the sum of weights of disconnected nodes minus the
cost of compromising a node. The defender’s payoff, on

•

the other hand, is expressed as the utility of deploying
a new node minus the sum of weights of disconnected
nodes, the time required to deliver the information to
the IoBT general sink, and the cost of deploying a
new node. Further, in the studied IoBT connectivity
problem, the defender must maintain the number of IoBT
devices sensing the same type of information above a
certain required threshold. Thus, the defender’s strategy
set is coupled with the attacker’s action at each time
epoch. Consequently, we cast the problem as a dynamic
multistage Stackelberg connectivity game in which, at
each stage of the game, the attacker acts as a leader, and
the defender acts as a follower. Due to the dependence
of the attacker’s and defender’s actions in each stage of
the game on the network state, the feedback Stackelberg
equilibrium (FSE) is used to solve the IoBT connectivity
game.
We analytically derive sufficient conditions for the IoBT
network to remain connected at each stage of the game
when the FSE solution is used. Numerical results show
that the expected number of disconnected sensors, when
the FSE solution is used, decreases up to 43% compared
to a baseline scenario in which a Stackelberg game with
no feedback is used, and up to 46% compared to a
baseline equal probability policy.

The paper is organized as follows: Section I describes the
adversarial IoBT system model. Section II presents the formulation of the IoBT connectivity game. Section III presents the
feedback Stackelberg solution of the IoBT game. Section IV
presents sufficient connectivty conditions of the IoBT network
when the FSE is used. Section V presents the simulations
results and analysis. Finally, conclusions are drawn in Section
VI. A complete list of the notations used is in Appendix A.
II. S YSTEM M ODEL
Consider an IoBT network composed of a set D of heterogeneous devices that can be of different types within a set K
of size K. Each IoBT device can possibly represent a vehicle,
a drone, a robot, a surveillance camera, a sensor dedicated for
a certain type of application, a sensor-actuator pair or soldier
equiped with wearable sensors. Each device of type τ ∈ K
encompasses Nτ sensors (and their corresponding actuators)
sensing a subset Hτ of a set I of types of information. Due
to the heterogeneity of the IoBT nodes, in terms of roles
and capabilities, we consider a hierarchical tree structure [15]
1
. The hierarchical IoBT structure provides scalability and
allows the system operator to easily add new devices, which is
suitable for a large-scale IoBT system. The area that the IoBT
network spans is divided into subareas A1 , A2 ,...AH . Within
each area Ah , devices sensing the same type of information
j ∈ I are organized into a cluster Djh . Thus, an IoBT device
equipped with multiple sensors can belong to several clusters.
Within each cluster, one of the devices is chosen to be a cluster
head (CH), and, thus, the rest of the devices transmit their
sensed data to the CH. The CH then collects the information
1 Although the hierarchical network structure is chosen, in general, our
proposed approach can accomodate any network topology

3

GS
LS
LS
Type 1
Information

Type 2
Information

Attacker

Fig. 1: An example of the considered IoBT hierarchical system
with two subareas and two types of information.
received from the devices in the cluster and sends it to a local
sink (LS) serving subarea Ah .
In each subarea Ah , multiple LSs can be deployed for
redundancy. At any time epoch t, only one LS is activated
in each subrea Ah . Deploying redundant LSs ensures that
there is a substitute for the activated LS in case of failure
or malfunction. At each time epoch t, each activated LS
processes its information and performs more sophisticated
operations such as augmented sensing and extraction of useful
information as requested by the global sink (GS). The GS
is a high end node that eventually processes the information
received from the activated LSs in order to identify events
requested by the military commanders and provide situational
awareness. Since the nodes in the considered IoBT are of
heterogeneous capabilities and roles, each node i is assigned a
weight wi depending on its importance. The weight wi of each
device i ∈ D of type τ is measured in terms of the number of
different sensors that the device includes i.e. wi = Nτ . LSs, on
the other hand, perform more sophisticated operations. Thus,
each LS i is assigned a weight wL,i that is higher than the
weights of the devices i.e. wL,i > max1≤τ ≤K Nτ .
In this IoBT, an attacker is interested in minimizing the
connectivity of the network to prevent the GS from detecting important events thus ultimately impairing its decisions.
To achieve this goal, the attacker chooses at each time t
to compromise i.e. gain control over one of the nodes in
B = ∪H
h=1 Lh ∪ D where Lh is the set of LSs in subarea Ah .
In order to compromise each node, an attacker needs to spend
time and computations to complete the attack [13]. Thus, it
is assumed at any time t, the attacker can only compromise
one of the IoBT nodes. Thus, at time t, the attacker chooses
the node which maximizes its payoff which is expressed as
the sum of weights of all nodes that will be disconnected
from the GS, and the cost of compromising each node. This
cost pertains to the resources needed to compromise any given
targeted node. Let cτ be the cost of compromising device
of type τ and cL be the cost of compromising an LS. The
attacker also incurs additional costs cCH and caL in order to
determine the CH of each cluster or the activated LS in each
subarea. The costs cCH and caL can represent, for example,
the security costs of intercepting the beacon messages sent by
the CH or the activated LS to the remaining devices. Thus,
the total cost of attacking device i of type τ in subarea Ah

PM
is given by: ci = cτ + j=1 xijh cCH whereM = |I| and
xijh = 1 indicates that device i is the CH of cluster Djh or
xijh = 0, otherwise. The total cost incurred by attacking LS
i in subarea Ah is given by: cL,i = cLS + yih caL where yih
is the indicator that LS i is activated in subarea Ah . In order
to thwart the attacks made at each time epoch t, the defender
can choose one of the following actions:
1) Deploys a new device of type τ in subarea Ah ;
2) Changes the cluster head in cluster Djh ;
3) Changes the activated LS in subarea Ah ;
4) Deploys a new LS in area Ah .
Action 1) helps in maintaining the number of sensors necessary to maximize the amount of useful information gathered
within an area. Actions 2) and 3) ensure the robustness of
the network in case the currently activated LS or CH fails or
is destroyed by the attacker. In practice, the newly deployed
devices are typically brought from a warehouse that is in
the proximity of the battlefield. Action 4) ensures that there
will always exist an LS that could serve the sensors in any
subarea in case the activated LS fails or is compromised by the
attacker. For actions 1) and 4), the defender will incur a cost of
deploying a device or an LS. Let dτ be the cost of deploying
a device of type τ and let dL be the cost of deploying an LS.
In an IoBT, the newly deployed devices and LSs are intially
stored, prior to deployment, in a storage facility (or a military
base) that is in the proximity of the IoBT network that is
assumed to be secured from the attacker.
The objective of the defender is to maximize a payoff that
captures the difference between the achieved utility and the
sum of its costs until the end of the military operation at time
epoch T . This maximization will be subject to the constraint
that the number of sensors Njh (t) sensing information of type
j in subarea Ah at each time epoch t does not fall below
a certain threshold Nth,jh . This constraint ensures that the
GS as well as the LSs obtain the necessary information of
type j in a certain subarea Ah . The utility achieved from
deploying a device of type τ in subarea Ah is expressed
in terms of the number of clusters that will restore their
numberPof sensors above the threshold and is given by
M
uτ = j=1 I(j ∈ Hτ )I(Njh (t) < Nth,jh ) where I(.) is an
indicator function. The utility achieved from deploying an LS
in subarea Ah is given by uL = B − Lh where Lh = |Lh |
and B is a constant that reflects the recommended number of
LSs in each subarea. The defender’s utility is the utility of
deploying a new device or an LS. The defender’s cost at each
time epoch t is expressed in terms of the sum of weights of
disconnected nodes, the time spent to deliver the information
to the GS, and the cost of deploying a new node.
Due to the clear dependence between the goals and the
actions of the attacker and the defender as well as the impact
of the attacker and defender’s actions on the IoBT network
graph, the problem will be formulated as a noncooperative
positional game [12] and [14], as explained next.
III. I O BT C ONNECTIVITY G AME
Connectivity games are game-theoretic models [12] that
capture situations which require the maintainenance and

4

restoration of the normal operations of a given network. Connectivity games typically involve two players: a constructor
who is responsible for restoration of nodes as well as the
addition of new nodes, and a destructor who removes nodes
from the network. The constructor in our game is the IoBT
defender whereas the destructor is the attacker. A connectivity
game [12] is an interactive game in which the constructor and
the destructor play in alternation until one of the players wins
the game. The winning condition for the constructor involves
maintaining the connectivity of the network. In particular,
there are two types of objectives considered in classsical
connectivity games [12]: 1) A safety objective in which the
constructor must maintain the connectivity of the network in
every step of the game and 2) A reachability objective in which
the constructor must obtain a connected network starting from
a disconnected network.
However, in the IoBT setting, the objective is not only to
maintain the network connectivity but also to maximize the
network efficiency (for example in terms of energy efficiency
and latency). Further, in the IoBT network, devices sense
different types of information, and in order to obtain the
necessary information of each type in a certain area, there is
a need to ensure that the number of devices sensing the same
type of information does not drop below a required threshold.
Moreover, in a real-world IoBT, there is a cost incurred when
a device is destroyed by the attacker or deployed by the
defender, which is not considered in a classical connectivity
game [12]. The heterogeneity of the IoBT devices, in terms
of their importance and roles, is also not taken into account
in classical connectivity games [12].
Given these requirements and characteristics of the IoBT
network, we consider an IoBT connectivity game that extends
classical connectivity games. The IoBT connectivity game
is formulated as a discrete-time deterministic dynamic game
(P, T , X , (Sa,t , Sd,t )t∈T ) with a finite number of stages,
where the set of players P includes the attacker and the
defender, and the set of stages T = {1, 2, ..., T }. In this IoBT
connectivity game, the defender must observe the attacker’s
action before choosing its optimal action in order to maintain the number of devices in each area above the required
threshold. Thus, the IoBT connectivity game is formulated
as a Stackelberg game in which, at each stage t of the
game, the attacker acts as the leader, and the defender acts
as the follower. The state space X = Xa × Xd is the
set of all IoBT networks observed by the attacker and the
defender up to stage T . The state of the game at stage t is
ψt = (ψa,t , ψd,t ) ∈ X where ψa,t is the network observed
by the attacker and ψd,t is the network observed by the
defender. The network state observed by the attacker is given
by: ψa,t = (Da (t), {La,h (t), 1 ≤ h ≤ H}, {Da,jh (t), 1 ≤
j ≤ I, 1 ≤ h ≤ H}, {fa,jh (t), 1 ≤ j ≤ I, 1 ≤ h ≤
H}, {sa,h (t), 1 ≤ h ≤ H}) where Da (t) represents the set
of devices, La,h (t) is the set of LSs in subarea Ah , Da,jh (t)
is the cluster of devices sensing information type j in subarea
Ah , fa,jh (t) is the index of the device that is the CH of
Da,jh (t), and sa,h (t) is the index of the activated LS in
subarea Ah . Similarly, the network state ψd,t observed by
the defender is given by: ψd,t = (Dd (t), {Ld,h (t), 1 ≤ h ≤

H}, {Dd,jh (t), 1 ≤ j ≤ I, 1 ≤ h ≤ H}, {fd,jh (t), 1 ≤
j ≤ I, 1 ≤ h ≤ H}, {sd,h (t), 1 ≤ h ≤ H}) where
Dd (t) represents the set of devices, Ld,h (t) is the set of
LSs in subarea Ah , Dd,jh (t) is the cluster of devices sensing
information type j in subarea Ah , fd,jh (t) is the index of the
device that is the CH of Dd,jh (t), and sd,h (t) is the index of
the activated LS in subarea Ah . fa,jh (t) and fd,jh (t) are set to
be zero if the CHs of Da,jh (t) and Dd,jh (t) are compromised,
respectively. Similarly, sa,h (t) and sd,h (t) are set to be zero
if the activated LS of subarea Ah is compromised in ψa,t and
ψd,t respectively. The defender and the attacker are assumed
to have perfect knowledge on the IoBT network. Assuming
perfect knowledge by the attacker about the IoBT network
allows the defender to account for the worst-case scenario as
is typical in existing works such as in [10].
In our game, the set of pure strategies of the attacker
Sa,t (ψt ) at stage t is Sa,t (ψt ) = {ad,i , i ∈ Da (t)}∪{aL,lh , l ∈
La,h (t), 1 ≤ h ≤ H}, where action ad,i corresponds to
destroying device i, and action aL,lh corresponds to destroying
LS l in subarea Ah . Due to the constraint on the number of
devices in each cluster, the strategy set of the defender at each
stage t is coupled to the attacker’s action at and is a function
of the network state ψt . Hence, the strategy set Sd (ψt , at ) of
the defender is

Sd,t (ψt , at ) =

{bd,τ h , ∀τ | j ∈ Hτ ∀j ∈ Yih (t)} if E1 (at ),
Qd ,
otherwise,
(1)

where condition E1 (at ) is at = ad,i ,
∃j s.t. i ∈
Da,jh (t), Na,jh (t) ≤ Nth,jh , the set Yih (t) = {j ∈ I |
i ∈ Da,jh (t), Nd,jh (t) < Nth,jh }, Nd,jh (t) is the number of
devices in cluster Dd,jh (t) in network ψd,t , Na,jh (t) is the
number of devices in cluster Da,jh (t) in network ψa,t , and
the set Qd is the set of all possible strategies of the defender
given by
Qd = {bc,ijh , i ∈ Dd,jh (t), 1 ≤ j ≤ M, 1 ≤ h ≤ H}
∪{bd,τ h , 1 ≤ τ ≤ K, 1 ≤ h ≤ H} ∪ {bL,h , 1 ≤ h ≤ H}
∪{ba,lh , l ∈ Ld,h (t), 1 ≤ h ≤ H}.

(2)

Action bd,τ h corresponds to deploying a new device of type
τ in subarea Ah , action bc,ijh corresponds to assigning device
i to be the CH of cluster Dd,jh (t), action bL,h corresponds
to deploying a new LS in subarea Ah , and action ba,lh
corresponds to activating LS l in subarea Ah . According to
(25), if the attacker destroys a device and causes the number of
devices in some clusters to drop below the required threshold,
the strategy set of the defender will only include the actions
of deploying a device that restores the number of devices in
each affected cluster to the required threshold. Otherwise, the
defender can choose to either change the CHs, change the LSs,
deploy a new device, or deploy a new LS. The evolution of
the attacker’s state ψa,t is given by

Da (t + 1) =

Da (t) \ {i} if at = ad,i bt 6= bd,τ h ,
Da (t),
otherwise,


La,h (t + 1) =

La,h (t) \ {l} if at = aL,lh , bt 6= bL,h ,
La,h (t),
otherwise,

(3)

(4)

5


 Da,jh (t) \ {i} if at = ad,i i ∈ Da,jh (t)
bt 6= bd,τ h ,
Da,jh (t+1) =
 D
otherwise,
a,jh (t),

fa,jh (t+1) =


0







(5)

if at = ad,i , i ∈ Da,jh (t), fa,jh (t) = i,
bt 6= bc,i0 jh

i
if bt = bc,ijh , at ∈ Sa (ψt ), i ∈ Da,jh (t),






fa,jh (t), otherwise,
(6)


0 if at = aL,lh , sa,h (t) = l, bt 6= ba,lh ,




l if bt = ba,lh , at ∈ Sa (ψt ),
sa,h (t + 1) =




sa,h (t), otherwise.

(7)

Similarly, the evolution of the defender’s state ψd,t is

Dd (t + 1) =

Ld,h (t+1) =

Dd (t) \ {i} if at+1 = ad,i bt 6= bd,τ h ,
Dd (t),
otherwise,

(8)

Cd,t (at , bt , ψt ) and Ud (at , bt , ψt ) in terms of each pair of the
attacker’s and defender’s pure strategies at and bt are given
in Appendix B.
To increase the uncertainty of its action and improve its
payoff, the attacker will use a mixed strategy q t at each stage
t, thus randomizing its choices across its pure strategies. The
defender, on the other hand, responds with a pure strategy bt
[17]. It is assumed that the defender can perfectly observe
the strategy of the attacker at each stage t. The objective
of the attacker is then to find the optimal mixed strategies
q 1 , q 2 , ..., q T that maximize the sum of its expected payoffs
until stage T
T
X
X
max
qat Pa,t (at , bt , ψt ) s.t. 1 · q t = 1 ∀t, (15)

q 1 ,q 2 ,...,q T

where qat is the probabilitiy with which the attacker chooses
action at . Similarly, the objective of the defender is to find
the optimal strategies b1 , b2 , ..., bT that maximizes the sum of
its expected payoffs up to stage T i.e.
max

Ld,h (t) \ {l} if at+1 = aL,lh , bt 6= bL,h ,
Ld,h (t),
otherwise,

t=1 at ∈Sa,t

b1 ,b2 ,...,bT

(9)


 Dd,jh (t) \ {i} if at+1 = ad,i i ∈ Dd,jh (t)
bt 6= bd,τ h ,
Dd,jh (t + 1) =
 D
otherwise,
d,jh (t),
(10)

T
X
X

qat Pd,t (at , bt , ψt ) s.t. bt ∈ Sd,t (ψt , at ) ∀t.

t=1 at ∈Sa,t

(16)
Since the attacker’s and the defender’s actions are coupled to
the current stage t and the state ψt , the feedback Stackelberg
equilibrium will be used as a solution, as discussed next.

IV. F EEDBACK S TACKELBERG S OLUTION
The
FSE
applies for situations in which the leader first

0
if
a
t+1 = ad,i , i ∈ Da,jh (t + 1),

chooses
its
strategy
at time instant t t, and, then, the follower



fa,jh (t + 1) = i, bt ∈ Sd,t (ψt , at ),

chooses
its
strategy
based
on the current state and the leader’s

fd,jh (t + 1) =
action.
In
the
proposed
IoBT
connectivity game, the strategy
i
if bt = bc,ijh , at+1 6= ad,i ,



sets
S
(ψ
)
and
S
(ψ
,
a
)
a,t
t
d,t
t t of both the attacker and the



defender depend on the current state ψt . Further, the defender
fd,jh (t), otherwise,
(11) strategy set Sd,t (ψt , at ) at time instant t is dependent only on
the attacker’s action at at the current time instant t according

0
if
a
t+1 = aL,lh , sd,h (t) = l, bt ∈ Sd,t (ψt , at ),

to (25) [16]. Thus, the FSE is a suitable solution for our



IoBT connectivity game. The FSE is subgame perfect and time
l if bt = ba,lh , at+1 6= aL,lh ,
sd,h (t+1) =

consistent. Thus, at each stage t of the game, the FSE considers



the
immediate payoff at stage t as well as the expected sum of
sd,h (t), otherwise.
(12) payoffs of the subsequent stages up to T , in contrast to static
The attacker’s payoff at each stage t is expressed in terms Stackelberg games which only consider the immediate payoff
of its utility which is the sum SD,t (at , bt , ψt ) of weights of at stage t. Hence, the FSE solution is obtained recursively
all nodes that will be disconnected from the GS, and the cost using dynamic programing and solving a Stackelberg game
Ca,t (at , bt ) of destroying node i, as follows:
at each stage t of the game. Further, the dynamic nature of
Pa,t (at , bt , ψt ) = SD,t (at , bt , ψt ) − νCa,t (at , bt , ψt ), (13) the FSE solution makes it adaptive to system changes at any
instant t. In [18], it is shown that the FSE remains stable
where ν is a normalization constant. The defender’s payoff under stochastic Markovian perturbations of the system. The
at stage t is expressed in terms of its utility minus its costs. robustness and adaptability of the FSE solution is desirable for
The costs include the sum of weights of disconnected nodes a dynamic IoBT system that is constantly subject to random
SD,t (at , bt , ψt ), the transmission time Λt (at , bt , ψt ) required changes due to adversarial conditions.
to deliver the information to the GS, and the cost of deploying
Let q = (q 1 , q 2 , ..., q T ) and b = (b1 , b2 , ..., bT ) be respeca new node Cd,t (at , bt , ψt ), as follows:
tively the strategy vectors of the attacker and the defender
respectively. The FSE strategy will be
Pd,t (at , bt , ψt ) = Ud,t (at , bt , ψt ) − ηSD,t (at , bt , ψt )
∗
∗
−µΛt (at , bt , ψt ) − λCd,t (at , bt , ψt ), (14) Definition 1. The strategy profile (q , b ) constitute a feedback Stackelberg equilibrium if ∀ψt ∈ X , t ∈ T ,
where η, µ and λ are normalization constants. For readability,
Ωa,t (q ∗t , b∗t , ψt ) = max
max Ωa,t (q t , bt , ψt ), (17)
the expressions of SD,t (at , bt ), Λt (at , bt , ψt ), Ca,t (at , bt , ψt ),
q t ∈Ma,t bt ∈Rd (q )
t

6

where Ma,t is the space of mixed strategies of the attacker at
stage t, Ωa,t (q t , bt , ψt ) is the expected payoff of the attacker
starting from stage t and for a state ψt , and Rd (q t ) is the
optimal strategy set of the defender to the mixed strategy q t
of the attacker and is given by
Rd (q t ) = {b0t s.t. b0t = arg max Ωd,t (q t , bt , ψt )},
bt

Ωa,t (q t , bt , ψt )

=

qat Ωa,t+1 (q ∗t+1 , b∗t+1 , ψt+1 (at , bt ))

X

qat Pa,t (at , bt ),

(19)

at ∈Sa,t

Ωd,t (q t , bt , ψt )

=

X

qat Ωd,t+1 (q ∗t+1 , b∗t+1 , ψt+1 (at , bt ))

at ∈Sa,t

+

X

qat Pd,t (at , bt ),

(20)

with Ωa,T +1 = 0, Ωd,T +1 = 0. From (18) and (20), we can
directly find the optimal action of the defender for a given
attacker action at stage t as follows.
Remark 1. Given an attacker strategy profile q t , the defender
chooses the action b0t such that
qat (Pd,t (at , bt ) + Ωd,t+1 (q ∗t+1 , b∗t+1 , ψt+1 (at , bt )))

at ∈Sa,t

≤

X
qat (Pd,t (at , b0t ) + Ωd,t+1 (q ∗t+1 , b∗t+1 , ψt+1 (at , b0t ))),

at ∈Sa,t

∀bt ∈ ∩at

s.t. qat >0 Sd,t (ψt , at ).

(21)

In order to find the optimal mixed strategy of the attacker
(i.e. the leader) at each stage t, the leader usually solves a
linear program for each particular strategy b0t chosen by the
follower (as in [19]). Then, it chooses, as optimal solution, the
mixed strategy of the optimization problem that has the highest
payoff. The proposed solution in [19] is considered when the
leader and follower’s actions are not coupled. However, in our
problem and as shown in (25), the follower’s strategy set is
coupled to the network state ψt and to the attacker’s action
at . In other words, if the follower chooses action b0t as its
optimal action and when the network state ψt , it means that the
attacker has chosen its action from the subset S 0 a,t (b0t , ψt ) of
the strategy set Sa,t . We define Jψa,t = {(j, h) s.t. Na,jh (t) =
Nth,jh }. Then, the set S 0 a,t (b0t , ψt ) is obtained as
(
S

0

0
a,t (bt , ψt )

=

Sa,t \ Ra,t , if Jψa,t 6= φ, b0t ∈ Vt ,
Sa,t ,
otherwise,

s.t.

X
qat = 1,

+ Ωa,t+1 (q ∗t+1 , b∗t+1 , ψt+1 (at , b0t ))),

at ∈S 0 a,t (b0t ,ψt )

X
qat (Pd,t (at , bt ) + Ωd,t+1 (q ∗t+1 , b∗t+1 , ψt+1 (at , bt )))
at ∈S 0 a,t (bt ,ψt )

≤

X
qat (Pd,t (at , b0t ) + Ωd,t+1 (q ∗t+1 , b∗t+1 , ψt+1 (at , b0t ))).(23)

at ∈S 0 a,t (b0t ,ψt )

In the proposed linear program, for each strategy b0t of the
defender and for a given state ψt , the attacker determines
the optimal probability for each one of its actions according
to (23) while taking into account the best response of the
defender defined in (21). The proposed linear program holds
under the assumption that the attacker has full knowedge of
the defender’s actions and payoffs at each time epoch t. The
conditions under which the IoBT network remains connected
are derived in the following section.
V. C ONNECTIVITY C ONDITIONS

at ∈Sa,t

X

X

qat (Pa,t (at , b0t )
qa,t
0
at ∈S a,t (b0t ,ψt )

∀bt ,

at ∈Sa,t

+

max

(18)

for every bt
∈
∩at s.t. qat >0 Sd,t (ψt , at ), where
Ωd,t (q t , bt , ψt ) is the expected payoff of the defender
starting from stage t. At an FSE, the expected payoffs at
stage t and for state ψt are computed recursively as
X

following linear program for each strategy b0t of the defender
and given a network state ψt

(22)

where Ra,t = {ad,i s.t. i ∈ Djh (t), (j, h) ∈ Jψa,t }, Vt =
Qd \ {bd,ih , ∀i s.t j ∈ Hi ∀j ∈ Yih (t)}, the set Yih (t) = {j ∈
I | i ∈ Da,jh (t), Nd,jh (t) < Nth,jh }, and the set Qd is
defined in (2). Thus, at each stage t, the attacker solves the

In the IoBT, maintaining connectivity at any time is critical
for the successful operation of the network. Thus, the safety
objective of connectivity games is more suitable to the IoBT
than the reachability objective. In our game, the connectivity
of the IoBT network is maintained at each stage t if the
attacker does not choose an action that causes disconnection.
Disconnection occurs if neither a cluster nor an entire subarea
gets disconnected from the GS. To determine the connectivity
conditions under which the IoBT network remains connected,
when the FSE solution is used, we first determine, for each
action b0t of the defender, the set ZD (b0t ) of attacker’s actions
that cause disconnection:


V1 ,


V , ,
2
ZD (b0t ) = S 0 a,t (b0t , ψt ) ∩

V3 ,


V ,
4

if
if
if
if

b0t
b0t
b0t
b0t

= bc,ijh ,
= bd,τ h ,
= ba,lh ,
= bL,h .

(24)

where the set V1 = {afj0 h0 (t) , j 0 6= j or h0 6= h}∪{ash (t) , ∀h},
V2 = {afjh (t) , ∀j, h} ∪ {ash (t) ∀h}, V3 = {afjh (t) , ∀j, h} ∪
{as0h (t) , h0 6= h} and V4 = {afjh (t) , ∀j, h} ∪ {ash (t) , ∀h}.
Thus, given that the optimal action of the defender is
b0t , disconnection does not occur if the attacker does not
choose an action from the set ZD (b0t ). Let Fd,t (at , bt ) =
and
Pd,t (at , bt ) + Ωd,t+1 (q ∗t+1 , b∗t+1 , ψt+1 (at , bt )))
Fa,t (at , bt ) = Pa,t (at , bt ) + Ωa,t+1 (q ∗t+1 , b∗t+1 , ψt+1 (at , bt ))).
The following proposition provides sufficient conditions for
the IoBT network to remain connected when the FSE solution
is used.
Proposition 1. The proposed FSE solution(q ∗ , b∗ ) maintains
connectivity of the IoBT network if for every ψt ∈ X , t ∈ T .
For each attacker’s action adt in ZD (b∗t ), there exists ant in
S 0 a,t (b∗t , ψt )\ZD (b∗t ) in which one of the following conditions
hold:
1) B3,t (b∗t ) = φ.

7

∗
d ∗
2) If B1,t (b∗t ) ∪ B2,t (b∗t ) 6= φ, W · Fa,t (an
t , bt ) > Fa,t (at , bt ).

3) If B1,t (b∗t )
minbt ∈B1,t (b∗t )

6=
φ, B2,t (b∗t )
6=
d ∗
Fd,t (ad
t ,bt )−Fd,t (at ,bt )
<
1,
n
n
∗
Fd,t (at ,bt )−Fd,t (at ,bt )
d ∗
Fd,t (ad
t ,bt )−Fd,t (at ,bt )
arg minbt ∈B1,t (b∗t ) Fd,t
n ∗
(an
t ,bt )−Fd,t (at ,bt )
d ∗
Fd,t (ad
t ,bt )−Fd,t (at ,bt )
≤ arg maxbt ∈B2,t (b∗t ) Fd,t (an ,bt )−Fd,t (an ,b∗ ) .
t
t
t

φ,

and

4) If B1,t (b∗t )
minbt ∈B1,t (b∗t )

φ,

and

6=
φ, B2,t (b∗t )
6=
d ∗
Fd,t (ad
,b
)−F
d,t (at ,bt )
t t
n ∗ ≥ 1,
Fd,t (an
t ,bt )−Fd,t (at ,bt )
d ∗
Fd,t (ad
t ,bt )−Fd,t (at ,bt )
arg maxbt ∈B2,t (b∗t ) Fd,t (an ,bt )−Fd,t (an ,b∗ ) ≥ 1.
t
t
t

VI. S IMULATION R ESULTS AND A NALYSIS

∗
5) If B1,t (b∗t ) ∪ B2,t (b∗t ) = φ, Fa,t (an
t , bt ) > 0.

where
n ∗
B1,t (b∗t ) = {bt ∈ Sdn,t | Fd,t (an
t , bt ) − Fd,t (at , bt ) ≥
d
d ∗
0, Fd,t (at , bt ) − Fd,t (at , bt ) ≥ 0},
n ∗
B2,t (b∗t ) = {bt ∈ Sdn,t | Fd,t (an
t , bt ) − Fd,t (at , bt ) <
d
d ∗
0, Fd,t (at , bt ) − Fd,t (at , bt ) ≤ 0},
n ∗
B3,t (b∗t ) = {bt ∈ Sdn,t | Fd,t (an
t , bt ) − Fd,t (at , bt ) ≥
d
d ∗
0, Fd,t (at , bt ) − Fd,t (at , bt ) < 0},

Sdn,t = Sd,t (ψt , adt ) ∩ Sd,t (ψt , ant ),
W =

bm
t =

d ∗
Fd,t (adt , bm
t ) − Fd,t (at , bt )
,
n
m
Fd,t (at , bt ) − Fd,t (ant , b∗t )




arg minbt ∈B1,t (b∗t )


arg max
bt ∈B2,t (b∗
t)

d ∗
Fd,t (ad
t ,bt )−Fd,t (at ,bt )
n ,b∗ ) ,
Fd,t (an
,b
)−F
(a
t
d,t
t
t
t

d ∗
Fd,t (ad
t ,bt )−Fd,t (at ,bt )
n ∗ ,
Fd,t (an
t ,bt )−Fd,t (at ,bt )

Proposition 1 shows that maintaining connectivity at each
time epoch t depends on the payoffs of the attacker and
the defender. Further, the payoff of the defender in (14)
depends on the IoBT network parameters. For example, the
time required to deliver the information to the GS is a function
of the IoBT network capacity, as shown in Appendix B, which
can be controlled by adjusting the transmission bandwidth in
a wireless setting. Thus, in order to maintain connectivity at
each time epoch t, the IoBT operator adjusts its payoffs such
that one of the conditions in Proposition 1 is met.

if C1 (b∗t ),
if C2 (b∗t ),

the condition C1 (b∗t ) = B1,t (b∗t ) 6= φ, B1,t (b∗t ) = φ, the
condition C2 (b∗t ) = B2,t (b∗t ) 6= φ, and the set Qd is defined
in (2).
Proof. Since the attacker uses mixed strategies in our problem,
disconnection does not occur at stage t if qat = 0 for every
at in ZD (b0t ), i.e. the actions in ZD (b∗t ) are dominated. In
[20, Corollary 4], the conditions are derived for the case in
which a variable has a zero value in any optimal solution for a
given linear program.
In particular,
Pn
Pn given a linear program of
the form max j=1 cj xj s.t.
j=1 aij xj ≤ bj , xj ≥ 0, the
variable xr = 0 in the optimal solution of the linear program
if there exists q 6= r such that one of the following conditions
hold:
1) I3 6= φ,
2) If I1 ∪ I2 6= φ then Hcq ≤ cr
c ≥ maxi∈I2 aair
3) If I1 6= φ and I2 6= φ then mini∈I1 b aair
iq
iq
4) if I1 ∪ I2 = φ then cq > 0,
where I1 = {i|aiq > 0 and air ≥ 0}, I2 = {i|aiq <
0 and air ≤ 0}, I3 = {i|aiq ≥ 0 and air < 0},

air
 arg min aiq if I1 6= φ,
k=

arg max aair
if I1 = φ and I2 6= φ
iq
 akr
 b akq c if I1 6= φ,
H=

arg max aakr
if I1 = φ and I2 6= φ
kq
Thus, by applying these conditions to each qat in ZD (b∗t )
our proposed linear program in (23), the result follows.

For our simulations, we consider an IoBT network containing 1000 devices of seven types: Type 1 corresponds
to a radiological sensor, type 2 corresponds to a chemical
sensor, type 3 corresponds to an infrared (IR) camera, type
4 corresponds to an explosives detector, type 5 corresponds to
a surveillance camera, type 6 corresponds to a mititary robot
containing a chemical sensor, a radiological sensor, an infrared
camera and an explosives detector, and type 7 corresponds to a
military unmanned vehicle containing a surveillance camera,
an IR camera, a radiological sensor and a chemical sensor.
The number of subareas considered is H = 5. The number of
LSs available in each subarea is Lh = 2, the weight of each
LS i is set to wL,i = 15, which is chosen to be greater than
the weight of any of the devices at a lower hierarchy level.
The threshold on the number of sensors in each cluster Djh
is set to Nth,jh = 15. The normalizing coefficients are set to:
µ = 100, ν = 1, and λ = 1. The costs of deploying a device
of type τ and an LS are set to be dτ = 0.5Nτ and dL = 50.
All normalization constants and cost values are chosen such
that the costs are comparable to the number of sensors. For
detailed analysis, the following scenarios are considered:
1) The cost of compromising an LS cL is varied between
0 and 200 in steps of 50. The considered value of the
cost caL of determining the activated LS by the attacker
is set to 0. The maximum number of stages considered
is T = 1, 2, 3, where T = 1 corresponds to the case of
Stackelberg equilibrium with no feedback (NFSE). The
cost of determining the CH is set to be cCH = 20 while
the cost of compromising a device of type τ is set to be
cτ = 0.5Nτ .
2) The cost of finding the CH is varied between 0 and
100 in steps of 20. The costs of compromising an LS
and determining the activated LS (caL , cL ) is set to
(100, 50). The maximum number of stages considered
are T = 1, 2, 3.
3) The maximum number of stages T is varied between
1 and 5 in steps of 1. The considered cost values are
cτ = 0.5Nτ and cCH = 20, and the LS costs (caL , cL )
are to set to (0, 50) and (150, 50), respectively.
Fig. 2 shows, for the NFSE, the FSE, and a baseline policy
which assigns equal probabilities to attacking the activated
LSs, the average probability pH of attacking the LS in the
subarea with the highest weight as a function of the cost cL
of compromising an LS. Fig. 2 first shows that the NFSE
probability of attacking the activated LS with the highest

Probability of attacking the LS
with highest weight

0.3

Stackelberg equilibrium (No feedback)
Feedback Stackelberg equilibrium, T=2
Feeback Stackelberg equilibrium, T=3
Equal probability policy

0.25
0.2
0.15
0.1
0.05
0

0

50

100

150

200

Cost of compromising a local sink

Expected number of disconnected
sensors per stage

Stackelberg equilibrium (No feedback)
Feedback Stackelberg equilibrium, T=2
Feedback Stackelberg equilibrium, T=3
Equal probability policy

160
140
120
100
80
60

0

50

100

150

0.2

Stackelberg equilibrium (no feedback)
Feedback Stackeleberg equilibrium, T=2
Feedback Stackelberg equilibrium, T=3

0.15

0.1

0.05

0

0

20

40

60

80

100

Cost of finding the cluster head

Fig. 2: Probability of attacking the LS with the highest weight
vs the cost of compromising an LS
180

Probability of attacking the CH
with highest weight

8

200

Cost of compromising a local sink

Fig. 3: Expected number of disconnected nodes respectively
vs the cost of compromising an LS
weight is 0.19 for cL values less than 100. In this case,
the attacker’s payoff obtained from attacking any activated
LS is considerably higher than the attacker’s payoff achieved
from attacking any other device. Thus, the attacker chooses
to compomise only the five activated LSs. As a result, the
NFSE mixed strategy of the attacker is comparable to the equal
probability policy. As cL increases to 150, the payoffs achieved
by attacking an activated LS and the CHs become comparable,
and the attacker chooses to attack both the LSs and the CHs.
Thus, the probability of attacking the LS with highest weight
decreases to 0.09. When cL increases further to 200, the payoff
resulting from attacking an activated LS becomes considerably
lower than the payoff achieved by attacking any of the CHs,
and, thus, the attacker chooses to attack only the CHs. Next,
when using the FSE with T = 2, the FSE probability of
attacking the activated LS with the highest weight decreases
to 0.163 for cL values less than 100. This is due to the fact
that, by using a FSE, the attacker, as well as the defender, will
take into account the expected sum of payoffs from t + 1 to
T , when computing the FSE probabilities at time t according
to (19). Thus, the attacker’s payoff received from an attack
on any IoBT node increases compared to the NFSE case,
which results in increasing the probability of attacking some
of the IoBT nodes which are not LSs. Hence, the probability of
attacking the LS having the highest weight decreases. Then,
the probability of attacking the LS with the highest weight
decreases as cL increases to 200. However, the probability is
higher than the case of the NFSE. This is because the expected
sum of payoffs achieved by attacking the LS with highest
weight increases compared to the NFSE according to (19).
Finally, when using the FSE with T = 3 and for cL values
less than 100, the probability pH decreases to 0.112 compared

Fig. 4: Probability of attacking the CH with the highest weight
vs the cost of compromising an LS
to the case with T = 2. This is because the expected payoff of
attacking any IoBT node increases with the number of stages
according to (19), which causes pH to decrease. Then, as cL
increases to 200, pH decreases, but it remains higher than the
case when T = 2, since the expected sum of payoffs received
from attacking the LS with the highest weight increases with
T.
Fig. 3 shows the average number ND of disconnected sensors per stage resulting from the NFSE, the FSE, and the equal
probability policy as function of the cost of compromising
an LS. First, using the NFSE and when cL ≤ 100, the
expected number of disconnected sensors is 141 since the
attacker chooses to compromise only the activated LSs. Also,
the expected number of disconnected sensors is slightly higher
than when the attacker chooses to attack each of the activated
LSs with equal probability, since this policy is not optimal.
Fig. 3 also shows that, for cL = 150, the expected number
of disconnected sensors decreases to 83 since the attacker
chooses to compromise either the LSs or the CHs. Thus, the
value of the expected number of disconnected sensors drops
below the value of the equal probability policy. When cL
increases to 200, the expected number of disconnected sensors
decreases to 62 since the attacker will now compromise CHs.
Next, using FSE with T = 2 and for cL < 100, ND decreases
by 9% compared to NFSE, since pH decreases as shown in
Fig. 2. Then, as cL increases to 200, the expected number of
disconnected sensors decreases yet becomes higher than the
NFSE case since pH is higher according to Fig.2. Finally,
when using the FSE with T = 3, the expected number ND
is 107 when cL < 100. This is because, for the considered
cost values, the probability pH decreases with T as shown in
Fig. 2. Then, as cL increases to 200, the expected number of
disconnected sensors decreases, but it remains greater than the
case in which T = 2. This is due to the fact that the probability
pH increases with T when cL is greater than 150 as shown in
Fig. 2.
Fig 4 shows the average probability pc,max of attacking the
CH of the cluster with highest number of sensors resulting
from the NFSE and the FSE versus the cost of finding the
CH. Using NFSE and when cCH is 0, pc,max is 0.17 since the
payoffs resulting from an attack on the CHs are the highest.
As the value of cCH increases to 40, pc,max decreases to
0.09 since the attacker chooses to compromise both LSs and
CHs. Then, pc,max becomes zero as cCH increases up to
100 since the payoffs achieved by compromising the CHs

Stackelberg equilibrium (No feeback)
Feedback Stackelberg equilibirum, T=2
Feedback Stackelberg equilibrium, T=3
Equal probability policy

160
140
120
100
80
60

0

20

40

60

80

100

Cost of finding the cluster head

Fig. 5: Expected number of disconnected sensors per stage vs
the cost of finding the CH
will be considerably lower than the payoffs obtained from
compromising the LSs. Hence, in this case, the attacker will be
compromising the LSs. Next, using the FSE with T = 2 and
when cCH is 0, pc,max is 0.155. Then, when cCH increases up
to 40, pc,max decreases to 0.078. Thus, when cCH is less than
40, the value of pc,max is less than its value when NFSE is
used. This is because the expected sum of payoffs achieved by
attacking any IoBT node is higher than the NFSE according
to (19), which yields a decrease in the probability pc,max . As
cL increases from 40 to 100, pc,max decreases yet its value
becomes higher than the NFSE. This is because the expected
sum of payoffs received from attacking a CH, when using
the FSE, is higher than the case in which the NFSE is used,
which causes the probability to remain positive. Finally, when
using the FSE with T = 3, pc,max varies similar to the case
in which T = 2. However, for cCH less than 40, pc,max is
smaller than the case when T = 2 since the expected sum of
payoffs achieved by attacking any IoBT node increases with
T . Also, for cCH greater than 40, pc,max is higher than the
case when T = 2 since the expected sum of payoffs obtained
from attacking a CH increases with T according to (19).
Finally, Fig. 4 shows that, for the equal probability policy,
the probability of attacking a CH is zero since the attacker
only compromises the activated LSs.
Fig. 5 shows, for both the FSE and the equal probability
policy, the average number of disconnected sensors ND per
stage versus the cost of finding the CH. When using the NFSE
and when cCH = 0, the expected number of disconnected
sensors is 63 since the attacker will be compromising the
CHs. Then, the expected number of disconnected sensors is
82 as the value of cCH increases to 40, since the attacker
will choose proper (non-deterministic) mixed strategies over
both the LSs and CHs. Then, as cCH becomes higher than 40,
the expected number of disconnected sensors increases to 141
and exceeds the value of the equal probability policy since
the attacker will be compromising the activated LSs and the
equal probability policy is not optimal. Next, when using the
FSE with T = 2 and when cCH = 0, the expected number of
disconnected sensors ND is 65. In this case, the value of ND
is slightly higher than the one resulting from the NFSE since
the probability of attacking an LS is positive with FSE. As
cCH increases to 40, the value of ND increases to 81. Then,
as cCH increases to 100, the value of ND increases to 129.
For cCH values higher than 40, the value of ND resulting
from FSE is lower than the NFSE case since the probability

Expected number of disconnected sensors

180

800

Stackelberg equilibrium (No feedback)
Feedback Stackelberg equilibrium
Equal probability policy

700
600
500
400
300
200
100

1

2

3

4

5

Maximum number of stages (T)

Fig. 6: Expected number of disconnected nodes respectively
vs number of stages
Expected number of disconnected sensors

Expected number of disconnected
sensors per stage

9

700

Stackelberg equilirbium (No feedback)
Feedback Stackelberg equilibrium
Equal probability policy

600
500
400
300
200
100
0

1

2

3

4

5

Maximum number of stages (T)

Fig. 7: Expected number of disconnected nodes respectively
vs number of stages
of attacking a device which is not a CH is positive with FSE.
When using the FSE with T = 3, the value of ND varies as
function of cCH in a similar way as when T = 2. Yet, when
cCH is 0, the value of ND is slightly higher than when T = 2.
This is because in this case the probability of attacking an LS
increases with T . Also, for cCH values greater than 40, the
value of ND is lower than when T = 2 since the probability
of attacking a device which is not a CH increases with T for
the considered cost values.
Figs. 6 shows, for the case when the LSs costs (caL , cL ) are
(0, 50), the expected number of disconnected sensors versus
the maximum number of stages T when FSE, the NFSE, and
the equal probabilitiy policy are used, respectively. The NFSE
solution corresponds to finding the Stackelberg equilibrium for
a one stage game played at each time epoch t (1 ≤ t ≤ T ). In
Fig. 6, the expected number of disconnected sensors increases
with the maximum number of stages using the three solutions.
However, the expected number of disconnected sensors, when
the FSE is used, increases at a rate considerably slower than
when either the NFSE or the equal probability power policy
are used. Thus, the results confirm that, using the FSE, the
number of disconnected sensors per stage decreases with T
as opposed to the NFSE in which the attacker chooses its
mixed strategy only over the LSs. The decrease in the number
of disconnected sensors when using the FSE reaches up to
43% compared to the equal probability policy and up to 46%
compared to the Stackelberg equilibrium with no feedback,
when T is 5.
Fig. 7 shows, for the case when the LSs costs (caL , cL ) are
(150, 50), the expected number of disconnected sensors versus
the maximum number of stages T when FSE, the NFSE solution, and the equal probabilitiy policy are used, respectively.
In this case, the expected number of disconnected sensors also

10

increases with the maximum number of stages using the three
solutions. However, the number of disconnected sensors using
the FSE is slightly higher than the case of NFSE. This is due
to the fact that, in the case of no feedback, the attacker’s mixed
strategy does not include attacking the LSs whereas, using the
FSE, the attacker’s mixed strategy includes attacking the LSs,
and the probability of attacking the LSs increases with the
number of stages. The increase in the number of disconnected
sensors reaches up to 14% when T is 5. Nonetheless, the
number of disconnected sensors, using the FSE, decreases by
47% compared to the equal probability policy.
Thus, Figs. 6 and 7 show that the FSE yields a significant
decrease in the number of disconnected sensors when the LS
costs are low. The performance is slightly degraded compared
to the NFSE when the costs of attacking the LSs increase.
However, the number of disconnected sensors remains significantly lower than the equal probability policy.
VII. C ONCLUSION
In this paper, we have considered the connectivity problem
in an Internet of Battlefield Things network in which an adversary attempts to cause disconnection by compromising one
of the IoBT nodes at each time epoch while a defender tries to
restore the connectivity of the IoBT by deploying new IoBT
nodes or changing the roles of nodes. We have formulated
the problem as a multistage Stackelberg game in which the
attacker is the leader and the defender is the follower. Due to
the reliance of the attacker’s and the defender’s actions on the
network state at each stage t, we have adopted the feedback
Stackelberg equilibrium to solve the game. We have obtained
sufficient condition to maintain connectivity at each stage t
when the FSE solution is used. Numerical results show that
the expected number of disconnected sensors, when the FSE
solution is used, decreases up to 46% compared to a baseline
scenario in which a Stackelberg game with no feedback is
used, and up to 43% compared to a baseline equal probability
policy.
R EFERENCES
[1] N. Suri, M. Tortonesi, J. Michaelis, P. Budulas, G. Benincasa, S. Russell,
C. Stefanelli, and R. Winkler, “Analyzing the applicability of internet of
things to the battlefield environment,” in Proc. of International Conference on Military Communications and Information Systems (ICMCIS),
Brussels, Belgium, May 2016, pp. 1-8.
[2] M. Tortonesi, A. Morelli , M. Govoni, J. Michaelis, N. Suri, C. Stefanelli,
and S. Russell“Leveraging Internet of Things within the military network
environment — Challenges and solutions," in Proc. of IEEE World Forum
on Internet of Things (WF-IoT), Reston, VA, Dec. 2016, pp. 111-116.
[3] P. P. Ray, “Towards an Internet of Things based architectural framework
for defence," in Proc. of International Conference on Control, Instrumentation, Communication and Computational Technologies (ICCICCT),
Dec. 2015, Kumaracoil, India, pp. 411-416.
[4] W. H. Lee, J. Choi, J. H. Lee, Y. H. Kim and S. C. Kim, “Distributed
Power Control-Based Connectivity Reconstruction Game in Wireless
Localization," in IEEE Communications Letters, vol. 21, no. 2, pp. 334337, Feb. 2017.
[5] A. Roy, A. Mondal and S. Misra, “Connectivity Re-establishment in
the Presence of Dumb Nodes in Sensor-Cloud Infrastructure: A Game
Theoretic Approach," in Proc. of IEEE 6th International Conference
on Cloud Computing Technology and Science, Singapore, Dec. 2014,
Singapore, Singapore pp. 847-852.
[6] L. Goratti, T. Baykas, T. Rasheed and S. Kato, “NACRP: A Connectivity
Protocol for Star Topology Wireless Sensor Networks," in IEEE Wireless
Communications Letters, vol. 5, no. 2, pp. 120-123, Apr. 2016.

[7] R. Dou and G. Nan, “Optimizing Sensor Network Coverage and Regional
Connectivity in Industrial IoT Systems," in IEEE Systems Journal, no.
99, pp. 1-10, May 2017.
[8] Z. Xu, L. Chen, C. Chen and X. Guan, “Joint Clustering and Routing
Design for Reliable and Efficient Data Collection in Large-Scale Wireless
Sensor Networks," in IEEE Internet of Things Journal, vol. 3, no. 4,
pp. 520-532, Aug. 2016.
[9] X. Zhao, Y. Zhang, C. Jiang, J. Yuan and J. Cao, “Mobile-Aware Topology
Control Potential Game: Equilibrium and Connectivity," in IEEE Internet
of Things Journal, vol. 3, no. 6, pp. 1267-1273, Dec. 2016.
[10] P. Y. Chen, S. M. Cheng and K. C. Chen, “Information Fusion to Defend
Intentional Attack in Internet of Things," in IEEE Internet of Things
Journal, vol. 1, no. 4, pp. 337-348, Aug. 2014.
[11] Y. Han, Y. Chen, B. Wang and K. J. Ray Liu, “Enabling Heterogeneous
Connectivity in Internet of Things: A Time-Reversal Approach," in IEEE
Internet of Things Journal, vol. 3, no. 6, pp. 1036-1047, Dec. 2016.
[12] S. Grüner, F. G. Radmacher, and W. Thomas. “Connectivity games over
dynamic networks,” in Theoretical Computer Science, vol. 493, Jul. 2013,
pp. 46-65.
[13] Y. Zhang, J. Zheng, and M. Ma, Handbook of Research on Wireless
Security, Information Science Reference, 2008.
[14] Z. Han, D. Niyato, W. Saad, T. Başar, and A. Hjørungnes, Game
Theory in Wireless and Communication Networks: Theory, Models, and
Applications, Cambridge University Press, 2012.
[15] W. Pawgasame, “A survey in adaptive hybrid wireless Sensor Network
for military operations,” in Proc. of 2016 Second Asian Conference on
Defence Technology (ACDT), Chiang Mai, Thailand, Jan. 2016, pp. 78-83.
[16] T. Başar and G. J. Olsder, Dynamic Noncooperative Game Theory, 2nd
Edition, Society for Industrial and Applied Mathematics, 1998.
[17] B. An, M. Tambe, A. Sinha. “Stackelberg Security Games (SSG) Basics
and Application Overview”, in Improving Homeland Security Decisions,
Cambridge University Press, 2016.
[18] T. Başar and A. Haurie, “Feedback equilibria in differential games with
structural and modal uncertainties,” Advances in Large Scale Systems,
ch. 1, pp. 163–201. JAE Press Inc., Connecticut, May 1984.
[19] V. Conitzer, “On Stackelberg mixed strategies,” Synthese, vol. 193, no.
3, pp. 689–703, Mar. 2016.
[20] D. A. Babayev and S. S. Mardanov,“Reducing the number of variables
in Integer and Linear Programming Problems ," in Computational Optimization and Applications, vol. 3, no. 2, pp. 99–109, May 1994.

A PPENDIX
A PPENDIX A: S UMMARY OF N OTATION
D
Set of IoBT devices.
K
Set of devices’ types.
K
Size of set K
I
Set of information types.
M
Size of set I
Nτ
Number of devices of type τ .
Hτ
Information set of a device of type τ .
Ah
IoBT subarea h.
Djh Cluster sensing information j in subarea Ah .
Nth,jh Minimum required number of sensors in cluster Djh .
wi
Weight of device i.
wL,i Weight of LS i.
Lh
Set of LSs in subarea Ah .
cτ
Cost of compromising a device of type τ .
cL
Cost of compromising an LS.
cCH Cost of determining the cluster head.
caL Cost of determining the activated LS.
dτ
Cost of deploying a device of type τ .
dL
Cost of deploying an LS.
P
Set of players.
T
Set of stages.
X
State space.
Sa,t Attacker’s strategy set at time t.
Sd,t Defender’s strategy set at time t.
ψt
State of the game at time t.

11

ψa,t Network observed by the attacker at time t.
Da (t) Set of devices in ψa,t .
Da,jh (t) Cluster Djh in ψa,t .
fa,jh (t) Index of the device that is CH of cluster Da,jh (t).
La,h (t) Set of LSs in subarea Ah at time t.
sa,h (t) Index of the activated LS in La,h (t).
ψd,t Network observed by the defender at time t.
Dd (t) Set of devices in ψd,t .
Dd,jh (t) Cluster Djh in ψd,t .
fd,jh (t) Index of the device that is CH of cluster Dd,jh (t).
Ld,h (t) Set of LSs in subarea Ah in ψd,t .
sa,h (t) Index of the activated LS in La,h (t).
at
Attacker’s action at time t.
bt
Defender’s action at time t.
ad,i Attacking device i.
aL,lh Attacking LS l in subarea Ah .
bc,ijh Assigning device i to be the CH of Djh .
bd,τ h Deploying a device of type τ in subarea Ah .
ba,lh Activating LS l in subarea Ah .
qt
Attacker’s mixed strategy at time t.
Pa,t Attacker’s payoff at time t.
Pd,t Defender’s payoff at time t.
SD,t Sum of weights of disconnected sensors at time t.
Λt
Delay to deliver the information at time t.

the single hop delay between i and j and is given by:
Λ(i, j) = Rmiji where Rij is the capacity of the link (i, j)
and mi is the packet size of node i.
•

If at = ad,i , bt = bd,kh0 , i ∈ Dh00 (t), h00 6= h0 ,
M
X

SD,t (at , bt ) =

I(i ∈ Djh00 (t) )(xijh00 (t)Wjh00 (t) + x̄ijh00 (t)),

j=1

Λt (at , bt ) = max z̄h (t)I(h 6= h0 ) max z̄jh (t)
1≤h≤H

1≤j≤M

×(I(i ∈
/ Djh (t))(Λjh (fjh (t), sh (t), Djh (t))
+I(i ∈ Djh (t))I(fjh (t) 6= i)(Λjh (fjh (t), sh (t), Djh (t) \ {i})
+Λg (sh (t))) + I(h = h0 ) max I(j ∈
/ Hk )(fjh0 (t), s0h (t), Djh0 (t))
1≤j≤M

+
+I(j ∈ Hk )Λjh0 (fjh0 (t), sh0 (t), Djh
0 (t)) + Λg (sh0 (t))),

+
where Dh (t) is the set of devices in subarea Ah , Djh
(t) =
Djh (t) ∪ {N (t) + 1}, and N (t) + 1 is the index of the
newly deployed device and N (t) is the total number of
devices.
•

If at = ad,i , bt = bd,kh0 , i ∈ Dh0 (t),
SD,t (at , bt ) =

M
X

I(i ∈ Djh0 (t), j ∈
/ Hk )xijh0 (t)Wjh0 (t)

j=1

+ I(i ∈ Djh0 (t), j ∈ Hk )xijh0 (t)(Wjh0 (t) + 1)
+ x̄ijh0 (t),
Λt (at , bt ) = max I(h = h0 )z̄h (t) max I(i ∈ Djh0 (t))I(fjh0 (t) 6= i)
1≤h≤H

A PPENDIX B: E XPRESSIONS OF PAYOFF F UNCTIONS
The expressions of SD,t (at , bt ), Λt (at , bt ) in terms of each
pair of the attacker’s and defender’s pure strategies at and bt
are given as follows.
•

SD,t (at , bt ) =

I(i ∈ Djh (t)) xijh (t)Wjh (t) + x̄ijh (t))

+(I(j ∈
/ Hk )z̄jh (t)Λjh0 (fjh0 (t), sh0 (t), Djh (t) \ {i}))
+I(h 6= h0 ) max z̄jh (t)Λjh (fjh (t), sh (t), Djh (t))
1≤j≤M

+ Λg (sh (t)).

If at = ad,i , bt = bc,kj 0 h0 ,
H X
M
X

•

If a = ad,i , bt = ba,kh00 ,


SD,t (at , bt ) =

h=1 j=1

H X
M
X

I(i ∈ Djh (t))(xijh (t)Wjh (t) + x̄ijh (t))

h=1 j=1

−zj 0 h0 (t)Wj 0 h0 (t),

+I(h = h00 )(−zh00 (t)Wh00 (t)),

Λt (at , bt ) = max z̄h (t) max (1 − I(h = h0 , j = j 0 ))z̄jh (t)
1≤h≤H

1≤j≤M

+
×(I(j ∈ Hk )z̄jh (t)Λjh0 (fjh0 (t), sh0 (t), Djh
(t) \ {i})

1≤j≤M

Λt (at , bt ) = max (I(h 6= h00 )z̄h (t) + I(h = h00 ))

×(I(i ∈ Djh (t))x̄ijh (t)Λjh (fjh (t), sh (t), Djh (t) \ {i})
+I(i ∈
/ Djh (t))Λjh (fjh (t), sh (t), Djh (t)))

1≤h≤H

× max I(i ∈ Djh (t))I(fjh (t) 6= i)

+I(h = h0 , j = j 0 )(I(i ∈ Djh (t))Λjh (k, sh (t), Djh (t) \ {i})
+(I(i ∈
/ Dj 0 h (t))Λjh (k, sh (t), Djh (t))) + Λg (sh (t)),

where for any variable x, x̄ = 1 − x, I(.) is the indicator
function. In this part, all the network variables pertains
to network ψa,t , and the index a is dropped for ease
of notation. xijh (t) is an indicator whether device i is
the CH in cluster Djh (t), fjh (t) is the CH of Djh (t),
sh (t) is the activated LS in subarea h, Wjh (t) is given
by Wjh (t) = Njh (t), zh (t) is an indicator if subrea Ah is
currently disconnected from the GS, zjh (t) is an indicator
if cluster Djh (t) is currently disconnected from the network, Λjh (fjh (t), sh (t), Djh (t)) is the time to transmit
the information from cluster Njh (t) to LS sh (t) and is
given by Λjh (fjh (t), sh (t), Djh (t)) = Λ(fjh (t), sh (t))+
maxn∈Djh (t) Λ(n, fjh (t)), Λ(fjh (t), sh (t)) is the time
needed to transmit the information from CH fjh (t) to
LS sh (t), Λ(n, fjh (t)) is the time needed to transmit the
information from device n to CH fjh (t), and Λg (sh (t))
is the time required to deliver the information from sh (t)
to the GS. For any two IoBT nodes i and j, Λ(i, j) is

1≤j≤M

×Λjh (fjh (t), sh (t), Djh (t) \ {i}))
−I(i ∈
/ Djh (t))Λjh (fjh (t), sh (t), Djh (t)) + Λg (sh (t)),

•

where Wh (t) is given by: Wh (t) =
If at = ad,i , bt = bL,h00 ,
SD,t (at , bt ) =

H X
M
X

P

i∈Dh (t)

wi +wL,sh (t) .

I(i ∈ Djh (t))(xijh (t)Wjh (t) + x̄ijh (t)),

h=1 j=1

Λt (at , bt ) = max z̄h (t) max I(i ∈ Djh )I(fjh (t) 6= i)
1≤h≤H

1≤j≤M

×Λjh (fjh (t), sh (t), Djh (t) \ {i}))
−I(i ∈
/ Djh )Λjh (fjh (t), sh (t), Djh (t))) + Λg (sh (t))).
•

If at = aL,mh0 , bt = ba,kh00 , h0 = h00 ,
SD,t (at , bt ) = −zh00 (t)Wh00 (t),
Λt (at , bt ) = max I(h = h0 ) max Λjh0 (fjh0 (t), k, Djh0 (t))
1≤h≤H

1≤j≤M

+I(h 6= h0 )z̄h (t)( max z̄jh (t)Λjh (fjh (t), sh (t), Djh (t))
1≤j≤M

+I(h = h0 )Λg (k) + I(h 6= h0 )z̄h (t)Λg (sh (t)).

12

•

If at = aL,mh0 , bt = ba,kh00 , h0 6= h00 ,
SD,t (at , bt ) = ymh0 (t)Wh (t) + ȳmh (t)wL,m − zh00 (t)Wh00 (t),

Λt (at , bt ) = max (I(sh0 (t) 6= m, h = h0 ) + I(h 6= h0 ))
1≤h≤H

×z̄h (t)(Λg (sh (t)) + max z̄jh (t)Λjh (fjh (t), sh (t), Djh (t)))
1≤j≤M

+I(h = h00 )( max z̄jh00 (t)Λjh00 (fjh00 (t), k, Djh00 (t)) + Λg (k)),
1≤j≤M

where ymh (t) is an indicator that LS m is the activated
LS in subarea Ah .
•

If at = aL,mh0 , bt = bL,h00 ,
SD,t (at , bt ) = ymh0 (t)Wh0 (t) + ȳmh0 wL,m ,
Λt (at , bt ) = max z̄h (t)(I(sh0 (t) 6= k, h = h0 ) + I(h 6= h0 ))
1≤h≤H

× max (z̄jh (t)Λjh (fjh (t), sh (t), Djh ) + Λg (sh (t)).
1≤j≤M

•

If at = aL,mh0 , bt = bd,kh00 , h0 6= h00 ,
SD,t (at , bt ) = ymh0 (t)Wh0 (t) + ȳmh0 (t)wL,m ,

Λt (at , bt ) = max (I(sh0 (t) 6= m, h = h0 ) + (h 6= h0 , h 6= h00 ))
1≤h≤H

×z̄h (t)

M
X

z̄jh (t)(Λjh (fjh (t), sh (t), Djh (t))

j=1
+
+I(h = h00 ))z̄h (t)( max I(j ∈ Hk )z̄jh (t)Λjh (fjh (t), sh (t), Djh
(t))
1≤j≤M

+I(j ∈
/ Hk )z̄jh (t)Λjh (jh (t), sh (t), Djh (t)) + Λg (sh (t))).
•

If at = aL,mh0 , bt = bd,kh00 , h0 = h00 ,
SD,t (at , bt ) = ymh (t)(Wh0 (t) + Nk ) + ȳmh0 (t)wL,m ,

Λt (at , bt ) = max (I(s0h (t) 6= m, h = h0 )z̄h (t)
1≤h≤H

+
×( max I(j ∈ Hk )z̄jh (t)Λjh (fjh (t), sh (t), Djh
(t))
1≤j≤M

+I(j ∈
/ Hk )z̄jh (t)Λjh (fjh (t), sh (t), Djh (t) + Λg (sh (t))))
+I(h 6= h0 )z̄h (t)( max z̄jh (t)Λjh (fjh (t), sh (t), Djh (t)) + Λg (sh (t))).
1≤j≤M

•

If at = aL,mh0 , bt = bc,kj 0 h00 ,

SD,t (at , bt ) = ymh0 (t)Wh0 (t) + ȳmh0 (t)wL,m ,
Λt (at , bt ) = max (I(sh (t) 6= m, h = h0 ) + I(h 6= h0 ))
1≤h≤H

×z̄h (t)( max I(h = h00 , j = j 0 )Λjh (k, sh (t), Djh (t))
1≤j≤M

+(1 − I(h = h00 , j = j 0 ))z̄jh (t)Λjh (fjh (t), sh (t), Djh (t))
+Λg (sh (t))).

The expressions of Ca,t (at , bt ), Cd,t (at , bt ) and
Ud,t (at , bt ) in terms of the pure strategies of the attacker
and the defender are given as follows:


ci ,
cL,k ,

di ,
Cd,t (at , bt ) = dL ,

0,

Ca,t (at , bt ) =

if at = ad,i ,
if at = aL,kh .
if bt = bd,ih ,
if bt = bL,h ,
otherwise.

The expression of the defender’s utility is given by

ui ,
Ud,t (at , bt ) = uL ,

0,

if bt = bd,ih ,
if bt = bL,h ,
otherwise.

