On The Survivability of Wireless Ad Hoc Networks With Node Misbehaviors and Failures

284 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 7, NO.
3, JULY-SEPTEMBER 2010
On the Survivability of Wireless Ad Hoc

Networks with Node Misbehaviors and Failures
Fei Xing, Student Member, IEEE, and Wenye Wang, Member, IEEE
Abstract—Network survivability is the ability of a network to stay connected under failures and attacks, which is a fundamental issue to
the design and performance evaluation of wireless ad hoc networks. In this paper, we focus on the analysis of network survivability in
the presence of node misbehaviors and failures. First, we propose a novel semi-Markov process model to characterize the evolution of
node behaviors. As an immediate application of the proposed model, we investigate the problem of node isolation where the effects of
denial-of-service (DoS) attacks are considered. Then, we present the derivation of network survivability and obtain the lower and upper
bounds on the topological survivability for k-connected networks. We find that the network survivability degrades very quickly with the
increasing likelihood of node misbehaviors, depending on the requirements of disjoint outgoing paths or network connectivity.
Moreover, DoS attacks have a significant impact on the network survivability, especially in dense networks. Finally, we validate the
proposed model and analytical result by simulations and numerical analysis, showing the effects of node misbehaviors on both
topological survivability and network performance.
Index Terms—Network survivability, node misbehaviors, semi-Markov process, node behavior modeling, node isolation problem,
k-connectivity, wireless ad hoc networks.
1 INTRODUCTION
N ETWORK survivability is an essential aspect of reliable

communication services. In the literature, the network
survivability has been defined from different perspectives
a number of works [8], [9], [10]. In addition, extensive
research efforts have been made to understand fundamen-
tal properties for asymptotic connectivity of wireless multi-
[2], [3], [4], [5], [6], [7], [8], [9], [10]. These network hop networks [12], [13], [14], [15], [16]. In these studies, a
survivability definitions provide a general intuitive notion common premise is that as long as a node has active
of the concept of survivability and are applicable for
neighbors, the node is connected to the network “physi-
traditional telecommunication networks, where traffic ca-
cally” via wireless links. Nevertheless, the premise can
pacity and service restorability are of main concerns.
However, they do not have the mathematical precision to hardly hold in real networks by considering potential node
lead to a quantitative characterization and do not grasp the misbehaviors and random failures. For example, selfish
fundamental aspect of the survivability of wireless ad hoc nodes may not forward control and/or data packets for
networks. Compared with traditional networks, wireless other nodes for the sake of saving their own energy and
ad hoc networks are more vulnerable to malicious attacks malicious nodes may launch denial-of-service (DoS) attacks
and random failures due to their unique features such as such as Jellyfish and Blackhole to interrupt normal routing
constrained node energy, error-prone communication and forwarding procedures. We notice that substantial
media, and dynamic network topology. Thus, as pointed works have been done to characterize various node
out in [11], it is the first major goal for a survivable wireless misbehaviors and evaluate their effects on network perfor-
ad hoc network to establish and maintain a connected
mance [17], [18], [19]. However, little research effort was
topology, whenever it is practical. Based on this observation,
made to analyze to what extent these node misbehaviors
as a fundamental topology property and prerequisite for all
networking operations, topology connectivity is a critical can impact the topological survivability of wireless ad hoc
index for the survivability of wireless ad hoc networks, networks quantitatively.
especially in the presence of malicious attacks and random Therefore, the presence of node misbehaviors and multi-
failures. ple failures yields new challenges to the survivability of
We notice that network connectivity has been used as a wireless ad hoc networks and motivates us to reveal their
metric in evaluating the survivability of ad hoc networks by fundamental impacts on network survivability. More pre-
cisely, in this paper, we perceive the survivability of a
wireless ad hoc network as the probabilistic k-connectivity
. F. Xing is with Cisco Systems, Bldg. 14, 4th Floor, Mail-stop 2, 3625 Cisco
Way, San Jose, CA 95136. E-mail: fexing@cisco.com.
and provide a quantitative analysis on the impacts of both
. W. Wang is with the Department of Electrical and Computer Engineering, node misbehavior and failure on network survivability. We
North Carolina State University, 3056 Engineering Building II, 890 Oval summarize the contributions of this work as follows:
Drive, P.O. Box 7911-EBII, Raleigh, NC 27606.
E-mail: wwang@eos.ncsu.edu. . A generic model based upon a semi-Markov process
Manuscript received 25 June 2007; revised 12 Mar. 2008; accepted 24 Oct. (SMP) is proposed to characterize the evolution of
2008; published online 6 Nov. 2008. node behaviors, and the stochastic property of the
For information on obtaining reprints of this article, please send e-mail to:
tdsc@computer.org, and reference IEEECS Log Number TDSC-2007-06-0081. model is analyzed to disclose the effects of node
Digital Object Identifier no. 10.1109/TDSC.2008.71. behaviors.
1545-5971/10/$26.00 ß 2010 IEEE Published by the IEEE Computer Society
XING AND WANG: ON THE SURVIVABILITY OF WIRELESS AD HOC NETWORKS WITH NODE MISBEHAVIORS AND FAILURES 285
. The node isolation problem is revisited by forwarding data packets or disrupting legitimate
examining the cooperative degree, and the probabil- path selections by broadcasting fake route replies.
istic k-connectivity of individual nodes is obtained . Failed state ðF Þ. In this state, a node is unable to
by using the stochastic property of node behaviors. initiate or respond to route discoveries.
. The survivability of wireless ad hoc networks is Particularly, we focus on two types of malicious
analyzed probabilistically, and its theoretical bounds behaviors in this paper: Jellyfish and Blackhole attacks [19].
are derived in closed forms, which enables us to Slightly different from the descriptions in the literature, in
quantify the impacts of different behaviors. this paper, the Jellyfish attack is referred as to any malicious
The remainder of this paper is organized as follows: In behavior that complies with all routing rules but reorders,
Section 2, we classify node behaviors and define the problem delays, or drops data packets, while the Blackhole attack is
of network survivability. In Section 3, we propose an SMP referred as to a brutal behavior that always claims the
model to characterize node behavior transitions. In Section 4, shortest path to the destination so that path selections and
we discuss the node isolation problem as a case study and all data traffic can be trapped later on. In the succeeding
derive the probability of node isolation. In Section 5, we find context, we refer to nodes launching these two attacks as
the closed-form approximation of network survivability by Jellyfish and Blackhole nodes, respectively.
deriving its theoretical bounds for k-connected networks.
In Section 6, we validate our findings by simulations and 2.2 Network Survivability Definitions
provide performance evaluations. In Section 7, we compare Various survivability definitions have been proposed in
our work with related works, followed by conclusions in different disciplines. For example, Ellison et al. defined
Section 8. survivability as the capability of a system to fulfill its mission,
in a timely manner, in the presence of attacks, failures, or
accidents [2]. In the updated Federal Standard 1037C [3],
2 PROBLEM FORMULATION survivability is defined as the property of a system, subsystem,
2.1 Preliminaries equipment, process, or procedure that provides a defined
2.1.1 Network Model degree of assurance that the named entity will continue to
function during and after a natural or man-made distur-
In this paper, N mobile nodes in a wireless ad hoc network
bance. While these definitions provide a good description of
are randomly and uniformly distributed over a 2D square
the concept of survivability, they do not have mathematical
with area A. The node transmission radius, denoted by r, is
precision to lead to any quantitative interpretation of
assumed to be identical for all nodes. Thus, the underlying
survivability. It is difficult to determine whether a given
communication graph of a wireless ad hoc network is
system is survivable, and it is difficult to compare the
modeled by a geometric random graph GðN ; rÞ [20], where
survivability of two systems [6].
N denotes the vertex set with jN j ¼ N, and an edge exists
A more general survivability definition was introduced
between two vertices only if their distance is no greater than
by Knight and Sullivan [4] for critical information systems
r. Analogous to GðN ; rÞ, a wireless ad hoc network is
as follows: A survivability specification is a four-tuple
denoted by MðN ; rÞ (or M for clarity). These denotations
fE; R; P; Mg, where E is the assumed operating environ-
will be used in the succeeding definitions and analysis.
ment for the system, R is a set of specifications of tolerable
2.1.2 Node Classification services to be provided by the system, P is a probability
distribution across R, and M is a finite-state machine (FSM)
In a wireless ad hoc network, node cooperation in a
defining tolerable service transitions. Although this defini-
routing process is an essential requirement to maintain
tion provides a comprehensive framework in defining the
protocol operations and network connectivity [21]. How-
survivability of critical infrastructure applications such as
ever, since every node is an autonomous system, it may
banking systems, it still lacks mathematical precision and
decide how to act in the network by itself. Considering the
leaves a number of open questions. For example, it did not
potential impacts of various misbehaviors, we extend the
take into account the impact of any failures. In addition,
geometric random graph model aforementioned by intro-
this definition can hardly be applied for wireless ad hoc
ducing an additional assumption that all nodes operate
networks since these networks are normally highly dy-
independently in the following four states:
namic systems without predefined specifications of toler-
. Cooperative state ðCÞ. In this state, a node complies able services R.
with all routing and forwarding rules, i.e., being able Other than the above qualitative definitions, we notice
to initiate and respond to route discoveries correctly that a variety of metrics has been used to define surviva-
and forward control and data packets for others at bility in wireless networks. For example, the survivability
the best effort. of wireless mobile networks was defined in [5] as a network
. Selfish state ðSÞ. In this state, a node can initiate and ability to perform its designated set of functions given
respond to route discoveries for its own purpose but network infrastructure component failures resulting in a
may not forward control or data packets for others service outage and measured by traditional registration
for the sake of power saving. blocking probability and call blocking probability. Ob-
. Malicious state ðMÞ. In this state, a node launches viously, this definition applies for cellular networks but not
DoS attacks on the network layer, e.g., being for ad hoc networks since blocking probabilities are not of
cooperative in the routing stage but reluctant in major concern in ad hoc networks. In another recent work,
286 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 7, NO. 3, JULY-SEPTEMBER 2010
the excess packet loss due to failures (ELF) was taken as the evolution of node behaviors, so that the stochastic property
survivability performance measure [6], which is essentially of node behaviors can be estimated from both complete and
a traditional network performance metric for data networks incomplete data in Section 3. Second, we reevaluate the
and not necessarily specific for wireless ad hoc networks. problem of node isolation by considering the scenario with
Therefore, network survivability must be defined con- node misbehaviors in Section 4.1, where the node isolation
cretely with mathematical precision for wireless ad hoc probability is proved to be a function of the stochastic
networks. In general, the topology of a wireless ad hoc property of node behaviors. Based on our study of node
network keeps changing dynamically due to various reasons isolation, we are able to reveal the impact of node behaviors
such as node mobility and channel randomness (i.e., on network survivability.
multipath fading, path loss, shadowing, etc.) even when
node failures or security attacks are not present. For wireless 3 NODE BEHAVIOR MODELING
ad hoc networks, maintaining a connected topology is an
In this section, we use an SMP to model the evolution of
important design issue; otherwise, no network operations
node behaviors and analyze the stochastic property of the
(such as routing and forwarding) can be guaranteed, not
node behavior model.
even, say, quality of service. As a result, whether a network
is survivable largely depends on whether outgoing paths 3.1 Node Behavior Transitions
are available for every node so that they can be used for Wireless ad hoc networks are complex and dynamic systems
communications. Thus, we consider the survivability of a due to unexpected random node behaviors. In real net-
wireless ad hoc network to be a basic network capability to works, the behavior of a node may change at any time due to
maintain a connected topology in the presence of malicious various reasons. For example, a node can be failed due to
adversaries and random failures and use connectivity as the energy depletion or even a turn-off of transceivers triggered
metric to define it as follows: by end users, or a node’s security can be compromised by
Definition 1. Given a wireless ad hoc network M, let ðMÞ other attackers so that the node is utilized to launch new
denote the (vertex)-connectivity of M. The network surviva- attacks. In this work, we assume that a node may change its
bility of M, denoted by NSk ðMÞ, is defined as the probability behavior as follows:
that all active (unfailed) nodes are k-connected, i.e., . A cooperative node is exposed to become failed
NSk ðMÞ ¼ P rððMa Þ ¼ kÞ; ð1Þ due to various reasons such as energy exhaustion,
misconfiguration, and so on. It is also prone to be
where Ma is the network induced by all active nodes of M. configured on purpose as a selfish one for the
sake of power saving or to be compromised as a
Note that in the definition above, we are particularly malicious node.
interested in the connectedness of active nodes, including . It is possible to convert a selfish node to be
cooperative, selfish, and malicious nodes. This is because of cooperative again by means of proper configura-
the fact that failed nodes, being unable to participate in tions. A selfish node can become malicious due to
routing operations, do not contribute to the topological being compromised or failed due to power depletion.
connectedness. . A malicious node can become a failed node, but it
will no longer be considered to be cooperative or
2.3 Problem Formulation selfish even if its disruptive behaviors are inter-
With the definition of network survivability, the problem mittent only.
studied in this work can be formulated as the Survivability to . A failed node can become cooperative again if it is
Node Misbehaviors (SNM): recovered and responds to routing operations.
SNM-Problem. Given a wireless ad hoc network M with The above assumptions do not specify any particular
four node behavior states described in Section 2.1, find out the reason for a behavior transition, so they can provide a
quantitative relationship between the four behaviors and the general exposure to the most common behavior transitions
network survivability, i.e., NSk ðMÞ, in closed forms. and are applicable to a wide range of network scenarios.
Intuitively, the solution to the SNM-Problem should Further, these assumptions are simple enough for us to
depend on basic network properties such as the number of model both node misbehaviors and failures in one mathe-
nodes ðNÞ and transmission radius r and stochastic (statistic) matical framework, which is presented next.
properties of node behaviors, such as the probability of a
3.2 Semi-Markov Node Model
node being in a certain state. Nevertheless, to the best of
our knowledge, little work has been done in modeling node Based on the node classification described in Section 2.1,

misbehaviors, which makes it difficult to estimate node we define a state space, S ¼ fCðcooperativeÞ; SðselfishÞ;
behavior properties. In addition, although a few works have MðmaliciousÞ; F ðfailedÞg and model node behavior transi-
studied the connectivity of ad hoc networks by analyzing the tions by a stochastic process, fZðtÞg associated with
node isolation probability where a node is isolated because space S. Because the future behavior depends on the
of no neighbors [15], [22], the impact of node misbehaviors current behavior but not on previous behaviors, if we let Xn
was never taken into account. Thus, it is quite challenging to denote the state at transition time tn , we have
solve the SNM-Problem and provide a closed-form approx-
imation for survivability. P rðXnþ1 ¼ xnþ1 j X0 ¼ x0 :; . . . ; Xn ¼ xn Þ
ð2Þ
In this work, we use a two-step approach to tackle the ¼ P rðXnþ1 ¼ xnþ1 j Xn ¼ xn Þ;
SNM-Problem. First, we use an SMP to characterize the
where xi 2 S for 0 i n þ 1. From (2), fXn ; n ¼ 0;

1; 2; . . .g constitutes a Markov chain with state space S.
However, the transition time from one state to another
state is totally based on the random behaviors of a node,
and it is very difficult to characterize transition times by
exponential distributions. For instance, a node is more
inclined to fail due to energy consumption as time passes,
and the less residual energy left, the more likely a node
changes its behavior to selfish. This implies that the future
action of a node may depend on how long it has been in
the current state, and transition intervals may have
arbitrary distributions.
Therefore, we use an SMP fZðtÞg to model node
behavior transitions [23], which is defined by
ZðtÞ ¼ Xn ; 8tn t < tnþ1 : ð3Þ Fig. 1. The SMP for node behavior evolution.
In (3), ZðtÞ refers to the state of the process during the
period from the most recent transition, and fXn g is called Finally, the state transition diagram of the homogeneous
the embedded Markov chain (EMC) of the process fZðtÞg. SMP fZðtÞg can be shown in Fig. 1. In the figure, state
The SMP model defined above enables us to consider transitions between states i and j for i, j 2 S are represented
the evolution process of node behaviors without the by edges associated with pij and Fij ðtÞ.
assumption of memoryless property; additionally, this One of the concerns for an analytic model is whether it
can be used to estimate or predict future behaviors. More
model can be used to describe a wide variety of random
important, the model itself must be sufficiently generic for
threats caused by node misbehaviors, depending on how
data diffusion, given complete or incomplete data. With the
to diffuse data into it. Specifically, let Tn ¼ tnþ1 tn be the
consideration of node misbehaviors, we intuitively perceive
sojourn time between the nth and ðn þ 1Þth transition, we
that the connectivity of a network will be affected by how
can define the associated (time-homogeneous) semi-Markov likely a node behaves cooperatively as time goes. Hence, we
Q ¼ ðQij ðtÞÞ by
kernel Q will show how to use our model to find state probabilities
(especially the probability of a node being in a cooperative
Qij ðtÞ ¼ P rðXnþ1 ¼ j; Tn tjXn ¼ iÞ ¼ pij Fij ðtÞ; ð4Þ status) at any time t > 0 for complete and incomplete data
traces next.
where pij ¼ limt!1 Qij ðtÞ ¼ P rðXnþ1 ¼ jjXn ¼ iÞ is the tran-
sition probability between states i and j, and Fij ðtÞ ¼ 3.3 State Distributions with Complete and
P rðTn tjXnþ1 ¼ j; Xn ¼ iÞ is the transition time distribu- Incomplete Data
tion from states i to j. The transient distributions of the SMP fZðtÞg, with state
Based on the assumptions in Section 3.1, the transition space S and semi-Markov kernel Q Q in (4), satisfy
probability matrix (TPM) of fXn g is given by
0 1 Pij ðtÞ ¼ P rðZðtÞ ¼ jjZð0Þ ¼ iÞ
0 pcs pcm pcf
XZ
t
B psc 0 psm psf C ð6Þ
IP ¼ B
@ 0
C; ð5Þ ¼ ð1 Hi ðtÞÞij þ Q_ il ðÞPlj ðt Þd;
0 0 1 A
l2S
1 0 0 0 0
P
where pii ¼ 0 means that fXn g only has transitions from a where Hi ðtÞ ¼ P rðTn < tjXn ¼ iÞ ¼ j2S Qij ðtÞ is the so-
state to another different state. In (5), a transition journ time distribution in state i, and ij is the Kronecker
probability of zero like pmc ¼ 0 or pms ¼ 0 means that a function and defined by one for i ¼ j and zero otherwise.
malicious node will not become cooperative or selfish, Without losing generality, we can assume that all nodes
in the network are cooperative at the initial time, i.e.,
according to our assumptions in Section 3.1. Since the
P rðZð0Þ ¼ cÞ ¼ 1. Then, the transient distribution Pcc ðtÞ is of
summation of transition probabilities to a state must be
particular interest, since it indicates the cooperativeness of
equal to one in a stochastic matrix, we know that pmf ¼ 1
any node at time t > 0. To calculate Pcc ðtÞ by using (6), the
and pfc ¼ 1 hold in (5) for this unity requirement. Recall
function Qij ðtÞ should be given in a closed form, which is,
that fZðtÞg is also associated with a number of transition
however, normally difficult to provide in a continuous-time
time distributions Fij ðtÞ, which are cumulative distribution domain [24]. Nevertheless, a numerical solution can be used
functions of transition times from states i to j. Based on the to solve (6) by rewriting the transient distributions in a
TPM defined in (5), we have Fii ðtÞ ¼ 1 and Fmc ðtÞ ¼ discrete-time domain as follows [24]:
Fms ðtÞ ¼ Ffs ðtÞ ¼ Ffm ðtÞ ¼ 1 since corresponding transition
probabilities are zero [23]. Nevertheless, determining other XX
m
Pij ðmhÞ ¼ ð1 Hi ðmhÞÞij þ hQ_ il ðxhÞPlj ðmh xhÞ;
transition time distributions is not trivial since they are l2S x¼1
dependent on further assumptions, real applications, and
ð7Þ
transition time measurements.
where h is the discretization step. In addition, Q_ il ðxhÞ can depending on many factors such as resource level, move-
be further approximated by the difference quotient as ment, and attack. By using a general SMP to model the
evolution of node behaviors, we are able to estimate either
1^
the transient or limiting probability of a node being in a
Q_ il ðxhÞ ¼ ^il ððx 1ÞhÞ for x > 1;
Qil ðxhÞ Q ð8Þ
h cooperative status, which will be shown to be a key factor
where Q ^il ðxhÞ is the empirical distribution of Qil ðÞ. impacting the connectivity of a network. Since limiting
By using this method, when all state transitions and probabilities ðPj Þ stand for long-term average distributions
of node behaviors and they are normally more accessible,
time instants of transitions are available, the difference
in the succeeding analysis, we use Pj (e.g., Pc ) directly.
quotient Q_ il ðxhÞ can be computed by (8), then Pij ðmhÞ
Nevertheless, when transient distributions Pij ðtÞ can be
can be computed by (7). Indeed, this method has already
computed based on sufficient trace data, all succeeding
been used in [25] to model behaviors of user mobility derivations still hold by substituting Pj with Pj ðtÞ with the
based on a tremendous trace database. assumption on the same initial state.
Unfortunately, to the best of our knowledge, there are no
complete trace data recording user behaviors in wireless
ad hoc networks. Thus, we strive to grasp the stochastic 4 NODE ISOLATION: A CASE STUDY
properties of node behaviors by utilizing any statistics One immediate effect of node misbehaviors and failures in
available and reasonable estimations to derive the limiting wireless ad hoc networks is the node isolation problem due to
state distributions. the fact that communications between nodes are completely
Let Ti be the sojourn time in state i, Tij be the transition dependent on routing and forwarding packets. In turn, the
time from states i to j, and E½ be the conventional
R1 notation problem of node isolation is a direct cause for network
for expectation;
R1 then, we have E½T i ¼ 0 ð1 Hi ðtÞÞdt and partitioning, which further affects network survivability.
E½Tij ¼ 0 ð1 Fij ðtÞÞdt. We have the following result. Traditionally, node isolation refers to the phenomenon in
Theorem 1. Given the SMP fZðtÞg associated with state space S which nodes have no (active) neighbors; however, we will
and TPM IP defined by (5), the transient distribution Pij ðtÞ show that due to the presence of node misbehaviors and
converges to a limiting probability Pj as t ! 1; further, Pj failures a node can be isolated even if active neighbors are
can be calculated by available. In this section, we present several typical cases for
this sophisticated problem first and then derive the
j E½Tj probabilistic connectivity of individual nodes.
Pj ¼ lim Pij ðtÞ ¼ P ; ð9Þ
l2S l E½Tl
t!1
4.1 Node Isolation Problem
¼< i > is the stationary distribution of fXn g.
where ~ A trivial case of node isolation occurs when a node
Proof. First, for the given EMC fXn g associated with the becomes failed. In this case, the failed node can be detected
state space S and t.p.m. IP defined by (5), it is trivial to by routing protocols normally and is said to be discon-
prove that fXn g is irreducible and positive recurrent. nected or isolated from the network. We study more
Thus, the SMP fZðtÞg is irreducible. Second, based on our general cases of node isolation by considering the follow-
ing three scenarios: 1) the effect of failed neighbors with no
assumptions in Section 3.1, a node works in any behavior
routing ability, 2) the effect of selfish neighbors with
state for a finite time, which implies that E½Ti < 1 and
P reluctance in forwarding (control) packets, and 3) the effect
i2S E½Ti < 1. Thus, the SMP fZðtÞg is positive recur- of malicious neighbors with intent of disrupting routing
rent as well. Finally, by [26, Theorem 9-3], the limiting operations.
probability exists and can be given by (9). u
t
4.1.1 Effect of Failed Neighbor(s)
Theorem 1 provides us a method to estimate the In Fig. 2a, suppose node x3 is a failed node. When node u
probability of a node being in a cooperative status when initiates a route discovery to another node v, the failed
we do not have a complete set of trace data. To calculate Pj , neighbor x3 is unable to forward the route discovery. When
we only need to estimate pij and E½Tij , which are normally all neighbors of u are failed, then u can no longer
easier to obtain from the statistics; then, we can use the communicate with other nodes. In this case, we say that u
following equations to calculate i and E½Ti : is isolated by its failed neighbors.
X X
¼~
~ IP; i ¼ 1; and E½Ti ¼ pij E½Tij : ð10Þ 4.1.2 Effect of Selfish Neighbor(s)
i2S j2S
In Fig. 2a, suppose node x3 is a selfish node. When node u
After i and E½Ti are obtained, we can use (9) to derive Pj , initiates a route discovery to another node v, the selfish
especially the cooperative probability Pc . neighbor x3 may be reluctant to broadcast the route request
In Section 4.1, we will provide a specific case study to show from u. In this case, x3 behaves like a failed node. It is also
how to estimate E½Tij and pij by using the statistics from possible for x3 to forward control packets; however, the
measurements and by using the assumptions on the network situation could be worse since u may select x3 as the next
itself. In addition, in Section 6.3, we will demonstrate how hop and send data to it. Consequently, x3 may discard all
transient distributions can converge to limiting probabilities data to be forwarded via it, then communications between
by using collected data from simulation experiments. u and v cannot proceed. When all neighbors of u are selfish,
In summary, due to node misbehaviors, the likelihood of u is unable to establish any communications with other
any node working cooperatively varies from time to time, nodes at a distance of more than one-hop away. In this case,
Fig. 2. Node isolation problem. (a) Failed or selfish neighbors. Fig. 3. Samples of outgoing paths of node u.
(b) Malicious neighbors.
Definition 2. For a pair of nodes ðu; vÞ, if the length of the
we say that a node is isolated by its selfish neighbors. Note shortest path between them is no less than two, i.e., u and v are
that selfish nodes can still communicate with other nodes at least two hops away, then all paths connecting u and v are
(via their cooperative neighbors), which is different from called the outgoing ðu; vÞ-paths for u or v.
failed nodes.
Fig. 3 illustrates this definition, where Fig. 3a shows
4.1.3 Effect of Malicious Neighbor(s) three outgoing ðu; vÞ-paths. The reason for having outgoing
Now, we consider the scenario where there is one or more path lengths larger than one hop is that the path with only
malicious nodes in the neighborhood of node u. Suppose one hop may not make a node able to communicate with
that in Fig. 2b node x2 is a Jellyfish node. Different from other nodes beyond its neighborhood. For example, when a
selfish nodes, Jellyfish nodes are always active in forwarding node u has selfish neighbors only, it is actually isolated by
control packets; however, if Jellyfish nodes are en route, they its selfish neighbors, thus having no outgoing ðu0 ; v0 ) paths,
will selectively or randomly drop data packets, reorder as shown in Fig. 3b.
packets, or increase jitters, which is especially harmful to With the definition of outgoing path, we further define
TCP traffic. Thus, if u has x2 as the next hop, then u will the cooperative degree, denoted by Dc ðuÞ, of node u as the
eventually lose communications with the nodes at least maximum number of outgoing paths of u. Note that the
two-hop away. In the case that all neighbors are Jellyfish cooperative degree does not necessarily equal to the number
nodes, node u is said to be isolated by malicious neighbors, of cooperative neighbors, due to the effect of Blackhole
which is similar to the case of having selfish neighbors. attacks, while when Blackhole nodes are not present, the
As mentioned in Section 2.1, we further consider maximum number of outgoing paths for a node is equivalent
Blackhole attacks in this paper due to their severe impact to the number of cooperative neighbors, and so is the
on network survivability. For example, as illustrated in cooperative degree.
Fig. 2b, suppose AODV is used as the routing protocol, Next, let ni ðuÞ be the number of node u’s neighbors at
when node u discovers the route to node v by broadcasting state i ði 2 SÞ and let nJ ðuÞ and nB ðuÞ be the numbers of
RREQ messages, a Blackhole neighbor, say, node x2 , can u’s Jellyfish and Blackhole neighbors, respectively; then, we
respond to u with a fake RREP message immediately can formulate the observation on the node isolation
claiming that it is in the optimal path or only one-hop away problem as follows:
to node v. Consequently, u selects x2 as the next hop and Proposition 1. Given node u with degree d, i.e., DðuÞ ¼ d, if
sends data to it, but x2 will just dump all packets. Without ns ðuÞ þ nf ðuÞ þ nJ ðuÞ ¼ d or nB ðuÞ 1, then the coopera-
proper countermeasures, just a single Blackhole node may tive degree is zero, i.e., Dc ðuÞ ¼ 0, and u is isolated from the
trap all traffic initiated from u whenever the destination is network.
beyond its one-hop neighborhood. Moreover, the Blackhole
node may be able to trap all traffic of its neighbors, which Now, Proposition 1 provides us with a direct method to
implies multiple node isolations in the worst case. find the probability of node isolation in a network with
Based on the above analysis, we know that node misbehaving nodes, which is calculated as follows:
misbehaviors and DoS attacks make node isolation a more
complicated problem and may affect the connectedness of P rðDc ¼ 0jD ¼ dÞ
every node. Next, we utilize the analysis above and the state ¼ P rðnB 1jD ¼ dÞ þ P rðns þ nf þ nj ¼ djD ¼ dÞ ð11Þ
distributions derived in Section 3 to derive the probabilistic ¼ 1 ð1 PB Þd þ ð1 Pc PB Þd ;
connectivity of individual nodes.
where Pc is the probability of a node being in a
4.2 Probability of Node Isolation cooperative state defined in Section 3, and PB is the
Based on the investigation of the node isolation problem, we probability of a node launching Blackhole attack. Note that
have an immediate observation that if a node does not have we omit the notation u since the derivation applies to any
cooperative neighbors or have at least one Blackhole neighbor, generic node u.
then the node is isolated from the network beyond its From (11), we see the direct impact of node misbehaviors
neighborhood. To present this observation in a formal way on the node isolation probability: the severer the node
and facilitate the derivation on the node isolation probability, misbehaviors present in a network, the less likely that a
we first define the outgoing path for a node. node’s neighbors are cooperative, and thus, the more likely
that the node is isolated from the network. For a given PB , present how to approximate the topological survivability
the cooperative probability Pc plays an important role in of a wireless ad hoc network in a closed form by using
determining the connectivity of individual nodes. For theoretical upper and lower bounds when node misbeha-
example, when Pc ¼ 0, P rðDc ¼ 0jD ¼ dÞ ¼ 1, which means viors and failures are present in the network. Before we
a node isolation because of no cooperative neighbors, and present our main result, we introduce the methodology of
when Pc ¼ 1, P rðDc ¼ 0jD ¼ dÞ ¼ 0, which means that node our solution first.
isolation is not caused by any node misbehaviors and
failures. 5.1 Methodology of Derivation
In fact, besides representing the node isolation prob- Let ðGÞ denote the minimum vertex degree of a graph G;
ability, the cooperative degree can be used to define the then, it is well known that ðGÞ ðGÞ [27], which implies
connectivity of individual nodes. Since a network is that the connectivity of a network is no greater than the
composed of individual nodes and its survivability is minimum number of neighbors of any node. Nevertheless,
largely dependent on the connectedness between nodes, in the random graph theory, it was proved in [28] that
evaluating the probabilistic connectivity of a generic node
will be one more step toward the analysis of network P rððGÞ ¼ ðGÞÞ ! 1: ð14Þ
survivability, described right next. The moral of this result is that a random graph G becomes
4.3 Probabilistic k-Connectivity of Individual Node k-connected at the instant when it achieves a minimum
degree of k with high probability (w.h.p.) [29]. However,
In this paper, a node is said to be k-connected to a
(14) holds for nongeometric random graphs, in which links
network if its cooperative degree is k. The physical
may exist between any pair of nodes regardless of node
meaning of this definition is that if a node’s cooperative
degree is k, then it may communicate with the nodes other distances. These results cannot be directly applied to
than its neighborhood via k disjoint outgoing paths. Thus, wireless ad hoc networks.
we have the following conclusion for the k-connectivity of Fortunately, a few recent literatures have shown that a
individual nodes. similar result also holds for geometric random graphs
[12], [14], [15], [20], [29], [30], [31]. Let %ðN ; kÞ and
Proposition 2. Given node u with degree d, i.e., DðuÞ ¼ d, u %ðN ; kÞ be the minimum (transmission radius) r at
is said to be k-connected to the network if its cooperative
which GðN ; rÞ is at least k-connected and has a minimum
degree is k, i.e., Dc ðuÞ ¼ k, which is satisfied only if u has
degree at least k, respectively. Then, it is proved in [30]
no Blackhole neighbor and has exact k cooperative
that for an arbitrary constant k ð1 k < NÞ, we have
neighbors, i.e., nB ðuÞ ¼ 0 and nc ðuÞ ¼ k.
lim P rð%ðN ; kÞ ¼ %ðN ; kÞÞ ¼ 1: ð15Þ
N!1
Proposition 2 enables us to derive the probability of a
node u being k-connected conditional on DðuÞ ¼ d: The above result implies that w.h.p. a network becomes

k-connected when the minimum node degree in the
P rðDc ¼ kjD ¼ dÞ ¼ P rðnc ¼ k; nB ¼ 0jD ¼ dÞ communication graph becomes k [29] and N goes to
¼ P rðnc ¼ k; nB ¼ 0; ns þnf þ nJ ¼ dkÞ: infinity. Based on this seminal result, it was shown that
ð12Þ Lemma 1 [14, Theorem 3]. For a geometric random graph G
with N vertices, the probability that G is k-connected
Since the events of any node being in a certain behavior
approximately equals to the probability that every vertex has
state are mutually independent, by the multinomial prob-
at least k neighbors, i.e.,
ability law, (12) can be rewritten as
P rððGÞ ¼ kÞ P rððGÞ kÞ ð16Þ
d
P rðDc ¼ kjD ¼ dÞ ¼ ðPc Þk ð1 Pc PB Þdk ; k 1: ð13Þ
k when N is sufficiently large and P rððGÞ kÞ is almost one.
Note that (13) holds for d k 1 only. When d < k,
This result has been verified by extensive simulations in
P rðDc ¼ kjD ¼ dÞ obviously is zero since the cooperative
[12], [14], [15], and [31]. Especially, it was shown in [12] that
degree cannot be more than the degree.
P rððGÞ kÞ is a good estimation for P rððGÞ ¼ kÞ even if N
Until now, we have analyzed the node isolation
is in the order of 50. Further, even when P rððGÞ kÞ is not
problem and revealed the direct impact of node misbeha-
close to one, it still provides a close approximation for
viors on the connectivity of individual nodes. Since node
isolation is a direct cause for network partitioning, we can P rððGÞ ¼ kÞ.
use the results in (11) and (13) as cornerstones to derive the The seminal results aforementioned offer us a meth-
network survivability. odology to find the topological survivability of wireless
ad hoc networks. However, due to the presence of node
misbehaviors, not every neighbor provides effective out-
5 NETWORK SURVIVABILITY ANALYSIS going paths, as discussed in Section 4.2. Hence, a
After modeling the evolution of node behaviors by an SMP necessary condition for a network to be k-connected is
and analyzing the impact of node misbehaviors on the that every node has at least k cooperative degree (or
connectivity of individual nodes, we are ready to solve the disjoint outgoing paths). Let ðMÞ denote the minimum
SNM-Problem defined in Section 2.3. In this section, we of the cooperative degrees of all nodes in a network M,

i.e., ðMÞ ¼ minfDc ðuÞ; 8u 2 Mg; then, we have the on the explanation above, we have an upper bound for
following lemma. NSk ðMÞ given by
Lemma 2. For a wireless ad hoc network M of N nodes in the !
\
presence of node misbehaviors, if M achieves a minimum NSk ðMÞ P r Dc ðuÞ k
cooperative degree of at least k and N is sufficiently large, then u2N D ð20Þ
M is k-connected asymptotically, i.e. N
¼ ð1 P rðDc ðuÞ < kÞÞr2 :
P rððMÞ ¼ kÞ P rððMÞ kÞ: ð17Þ
Thus, once we obtain the distribution function of
cooperative degree, we can calculate the upper bound
Proof. Since Dc ðuÞ DðuÞ 8u 2 M, then ðMÞ ðMÞ, of survivability.
which indicates that P rððMÞ kÞ P rððMÞ kÞ. Next, we explain how to obtain a lower bound for
Further, the connectivity cannot be greater than the survivability. We first rewrite (19) as
minimum cooperative degree, i.e., ðMÞ ðMÞ; !
thus, ðMÞ ðMÞ ðMÞ. Thus, P rððMÞ ¼ kÞ [
NSk ðMÞ 1 P r Dc ðuÞ < k : ð21Þ
P rððMÞ kÞ P rððMÞ kÞ holds in general. Based
u2Ma
on (1) given in Definition 1, the lemma follows. u
t
Recall that the network survivability has been defined in Let Na denote the number of active nodes in the network
(1) as the probability that all active nodes are k-connected to and 1fEg denote the indicator function; then, we can bound
a network. By Lemma 2, the survivability of a network M P rð[u2Ma Dc ðuÞ < kÞ from above by using Boole’s inequality:
can be given by the probability that all active nodes have at !
[
least k cooperative degree, i.e., Pr Dc ðuÞ < k ¼ E E 1SNa jNa
Dc ðuÞ<k
u¼1
u2Ma
NSk ðMÞ P rððMa Þ kÞ; ð18Þ " #
X
Na

ð22Þ
E E 1fDc ðuÞ<kg
where Ma is the subnetwork of M induced by all active
u¼1
nodes. Based on the above equation, we are ready to derive
¼ E½Na P rðDc ðuÞ < kÞ:
the bounds for network survivability next.
Notice that the expected value of Na is actually equal to
5.2 Bounds of Network Survivability
Nð1 Pf Þ, i.e., E½Na ¼ Nð1 Pf Þ, where Pf is the (limit-
Although (18) offers a guideline for deriving NSk ðMÞ, it is
ing) probability of a node being in the failed state, defined
quite challenging to find the distribution of ðMa Þ. Indeed,
in (9). We obtain a lower bound for NSk ðMÞ as
P rððMa Þ kÞ is equivalent to the joint probability of every
active node being at least k-connected to the network, i.e., NSk ðMÞ 1 Nð1 Pf Þ P rðDc ðuÞ < kÞ: ð23Þ
!
\ Again, to solve (23), we need to determine P rðDc < kÞ.
NSk ðMÞ P r Dc ðuÞ k : ð19Þ By the total probability law, P rðDc < kÞ is given by
u2Ma
X
1
We notice that it has been shown that some random graph P rðDc < kÞ ¼ P rðD ¼ dÞP rðDc < kjD ¼ dÞ: ð24Þ
models do not generate the correlation of the degrees in a pair d¼0
of adjacent nodes [32]; however, this noncorrelation does not Now, we need to find P rðD ¼ dÞ and P rðDc < kjD ¼ dÞ.
imply the independence of node degrees and even coopera- First, to derive P rðD ¼ dÞ, we use the (de)Poissonization
tive degrees. Considering that deriving the joint probability technique presented in [20] and [30]. As we mentioned
is actually intractable, we approximate the survivability by previously, the communication graph of a network M is
finding its asymptotic upper and lower bounds. associated with a homogeneous Poisson process H with
To provide an upper bound, recall that our network density ¼ N=A. Since we are particularly interested in the
model described in Section 2.1 is a geometric random graph topological survivability of active nodes, let A0 ¼ r2
GðN ; rÞ, in which N vertices are uniformly and randomly denote the area covered by a node’s transmission range;
distributed on a 2D square with area A. The vertex set can it is known that the number of active nodes within A0 is a
actually be represented by a (homogeneous) Poisson point Poisson random variable with density A0 ðNa =AÞ. Thus,
process H with density ¼ N=A. Based on the definition P rðD ¼ dÞ can be approximated by
of a (homogeneous) Poisson point process, the numbers of
points within disjoint subareas are mutually independent da a
P rðD ¼ dÞ ¼ e ; ð25Þ
random variables (with identical distribution). Thus, we can d!
find N=ðr2 Þ (active) points, denoted by N D , so that their where ¼ r2 Nð1 Pf Þ=A is the Poisson density. A similar
transmission ranges ðr2 Þ are disjoint (nonoverlapped) result was also presented in [15], in which more general
subareas (disks). As a result, the degrees of two nodes u results were presented for nonuniform node distributions.
and v are mutually independent as u, v 2 N D . Similarly, Second, we derive P rðDc < kjD ¼ dÞ. Since the coopera-
Dc ðuÞ and Dc ðvÞ are mutually independent as well. Based tive degree cannot be greater than the degree for any node,
P rðDc < kjD ¼ dÞ is always equal to one when d < k. When The third item on the RHS of (30) is given by
d k, P rðDc < kjD ¼ dÞ ðk 1Þ can be calculated by
X k1
1 X
d da a
X
k1 Pcm ð1 Pc PB Þdm e
m d!
P rðDc < kjD ¼ dÞ ¼ P rðDc ¼ mjD ¼ dÞ d¼k m¼0 ð32Þ
m¼1 ð26Þ ðk; a Pc Þ ðk; a ð1 PB ÞÞ
¼ ea PB ea PB :
þ P rðDc ¼ 0jD ¼ dÞ; ðkÞ ðkÞ
in which P rðDc ¼ 0jD ¼ dÞ is the node isolation probability By combining (31) and (32), we have (30) simplified as
given by (11) and P rðDc ¼ mjD ¼ dÞ is the probability of a
node being k-connected given by (13). By substituting (11) ðk; a Pc Þ
P rðDc < kÞ ¼ 1 ea PB 1 : ð33Þ
and (13) into (26), we can rewrite (26) as ðkÞ
k1
X Finally, by substituting (33) into (20) and (23), we obtain
d
P rðDc < kjD ¼ dÞ ¼ 1 ð1 PB Þd þ Pcm the asymptotic upper and lower bounds of network
m ð27Þ
m¼0 survivability given by (28) and (29), respectively. u
t
dm
ð1 Pc PB Þ : The above theorem answers the SNM-Problem defined
Thus, by utilizing (25) and (27), P rðDc < kÞ can be in Section 2.3 and quantifies the impact of different node
obtained from (24), and the upper and lower bounds of the behaviors on survivability directly. From the upper and
network survivability can be further obtained from (20) and lower bounds given in (28) and (29), respectively, we have
(23). We present our main result next. the following observations by numeric analysis:
5.3 Main Result and Implications 1. In general, the survivability is increasing in the
Theorem 2. For a wireless ad hoc network M in the presence of cooperative probability Pc , which is accordant with
node misbehaviors and failures, when the number of nodes N is our intuition. When the network area A is fixed, the
sufficiently large, the network survivability defined in (1) is higher the number of nodes N is, the higher the
upper bounded asymptotically by survivability is, due to the increased density. While
N if the density is fixed, increasing N will reduce the
ðk; a Pc Þ r2 survivability. This implies that it will become more
NSk ðMÞ ea PB 1 ð28Þ
ðkÞ difficult to achieve the same survivability level as a
and lower bounded asymptotically by network scale gets larger without increasing node
density accordingly.
a PB ðk; a Pc Þ 2. Given two networks M1 and M2 with the same
NSk ðMÞ 1 Nð1 Pf Þ 1 e 1 ;
ðkÞ N, , and Pc , besides cooperative nodes, suppose
ð29Þ that M1 has failed nodes only and M2 has
misbehaving (selfish and Jellyfish) nodes only; then,
where a ¼ Nð1 Pf Þ=ðr2 Þ, is the node density, and NSk ðM1 Þ < NSk ðM2 Þ always holds. The severer
Ph1 l
ðhÞ ¼ ðh 1Þ! and ðh; xÞ ¼ ðh 1Þ!ex l¼0 x =l! are the impact of node failures is due to the fact that node
complete and incomplete Gamma functions, respectively. failures are also isolated from the network, which
Proof. By considering P rðDc < kjD ¼ dÞ ¼ 1 for k > d and reduces the density of active nodes (e.g., a ).
substituting (25) and (27) into (24), P rðDc < kÞ is 3. For a given N, Pf , and Pc , both the upper and lower
bounds of the survivability decrease almost exponen-
given by
tially in a PB . An interesting observation is that when
X
k1 X
1 PB is not zero, a network with higher density can have
P rðDc < kÞ ¼ P rðD ¼ dÞ þ P rðDc < kjD ¼ dÞP rðD ¼ dÞ a lower survivability. Recall that in Section 4.1, we
d¼0 d¼k have mentioned that a Blackhole node may mislead
X1
da a X 1
ða ð1 PB ÞÞd a path selections of its neighborhood and trap sur-
¼ e e
d! d! rounding traffic; thus, the negative impact of Blackhole
d¼0 d¼k
k1
nodes will be exaggerated if they are located in the
X 1 X
d d
þ Pcm ð1 Pc PB Þdm a ea : area with high density.
d¼k m¼0
m d! Note that in real networks, the nodes at the vicinity of the
ð30Þ network (simulation) boundary have fewer (active) neigh-
bors and thus become isolated easily, which is known as the
The first item on the right-hand side (RHS) of (30) is
border effect. As pointed out in [31], the border effect is
equal to one. By using the complete Gamma function
negligible in the analysis if the network area is much larger
ðhÞ and incomplete Gamma function ðh; xÞ, the second
than the transmission coverage area of a single node and the
item on the RHS of (30) can be simplified as
node density is not high. Since the survivability bounds
X 1
ða ð1 PB ÞÞd a a PB ðk; a ð1 PB ÞÞ given in (28) and (29) are all asymptotic for a sufficiently
e ¼e 1 :
d! ðkÞ large N and we are particularly interested in large-scale
d¼k
extended networks (with fixed density) [31], the border
ð31Þ
effect is not considered in our derivation. For further
discussions on the border effect, readers are suggested to and expected sojourn times ðE½Ti Þ. Since these parameters
refer to [15] and [31] and the references therein. are dependent on specific application scenarios, we first
Remark 1. It is a premise that P rðDc < kÞ < 1=Nð1 Pf Þ establish an example network scenario and incorporate the
should hold to guarantee a positive lower bound following policies in our case study and succeeding
given in (29); otherwise, the lower bound is zero. simulations:
When P rðDc < kÞ ¼ oð1=NÞ, we have the following
. Every node has the same initial energy Einit and may
approximation:
turn off the packet forwarding functionality once its

ðk; a Pc Þ residual energy (normalized by Einit ) is below a
1 Nð1 Pf Þ 1 ea PB 1 threshold .
ðkÞ
Nð1Pf Þ ð34Þ . A simplified version of the nuglet counter [21] scheme
ðk; a Pc Þ
ea PB 1 ; is implemented to stimulate selfish nodes to be
ðkÞ cooperative again. In this scheme, each node pos-
and the left-hand side (LHS) is always less than the RHS sesses a positive number of tokens Iinit initially,
in the above equation as N P rðDc < kÞ 1. Since the earns tokens when it forwards packets for other
upper bound given in (28) is quite loose, we conjecture nodes, and spends tokens when it sends or receives
that the RHS of (34) is a tight upper bound for network its own packets. We assume that every selfish
survivability. Indeed, if cooperative degrees, Dc ðuÞ, are node spends I tokens on the average per unit time
assumed to be independent (as independent degrees (e.g., 1 second).
assumed in [14]), the RHS of (34) becomes the closed- . Each cooperative or selfish node has an equal
form approximation for network survivability. probability to be compromised by an exterior
attacker, which can start to compromise a node at
Remark 2. A special case of our result in Theorem 2 is that all any (random) time. The time to compromise a node
nodes are cooperative and node isolations are due to the is assumed to be Ta on the average. Once a node is
lack of neighbors only. In this case, the survivability of a compromised, it becomes malicious.
network can be simplified to ð1 ðk; r2 Þ=ðk 1Þ!ÞN . The time that any node resides in the network
by considering (29) and (34), which is the exact (called residence time) is random, depending on the
probabilistic k-connectivity approximation given in movement pattern of individual nodes, but with a
[14]. This indicates that our result provides a more finite expected value Tin . A node is claimed to be
generalized quantitative evaluation on the topological failed once it leaves the network.
survivability. Moreover, our result, especially the lower . At last, we assume an average recovery time TR so
bound, is of interest not only for theoretical analysis but that failed nodes can become operative again (e.g.,
also for practical design of survivable wireless ad hoc by recharging the battery or rejoining the network).
networks. For example, if the statistics of user behaviors
are available, we can use the methods proposed in
Remark 3. The above network scenario is simple enough for
Section 3 to estimate state probabilities. Then, given a
us to validate our analytical models, while it is general
desired survivability preference (e.g., > 0.9), the mini-
enough to represent a wide range of network scenarios
mum cooperative degree or the number of nodes can be
calculated as theoretical guidances to determine a proper by tuning parameters properly and can be extended to
network deployment so that the survivability preference more complicated scenarios by adding more factors.
can be achieved w.h.p.
Given the above scenario, two methods are used in this
Up to now, we have solved the SNM-Problem by paper to estimate pij and EðTi Þ (or E½Tij ).
providing the loose upper and tight lower bounds to
approximate the network survivability in closed forms, in
6.1.1 Empirical Estimation
which the impacts of node misbehaviors and failures can be The empirical estimation largely depends on the statistics of
evaluated directly. Next, we conduct exhaustive simula- the data collected from real measurements or simulation
tions to confirm our analytical result. experiments. First, we use the method proposed in [24] to
determine pij as follows: given the time period ½0; t, record
the total number of transitions from state i to all other
6 SCENARIO STUDY AND SIMULATION RESULTS
states k and denote it by nik ði; k 2 S; k 6¼ iÞ, then pij is
In this part, we provide simulation results of limiting P
approximated by nij = k2S nik . Next, we estimate the
probability estimation, bounds of network survivability, expected transition time E½Tij by using the average value
and the impact of misbehaviors on network performance. of all observed transition time (from states i to j) of all
6.1 Scenario Study nodes. Note that E½Ti is derivable from pij and E½Tij by
P
Recall that we have proposed a semi-Markov node behavior using (10), i.e., E½Ti ¼ j2S pij E½Tij . Obviously, the accu-
model and provided (9) as the solution for the limiting state racy of this empirical method depends on the size of data
probability (Pj for j 2 S ¼ fC; S; M; F g) in Section 3. Even set; in other words, the more the nodes and the longer the
with this formula, calculating Pj is a nontrivial task due to time we can observe, the closer the obtained average values
the difficulty in determining the transition probabilities ðpij Þ can approach to their expectations.
6.1.2 Heuristic Estimation TABLE 1

In this method, we determine pij by using the same way Default Values of Parameters
described in the empirical estimation since no heuristic is
known so far to provide an analytical solution of transition
probabilities. Nevertheless, given the above network sce-
nario, we can estimate expected transition times by using
the following heuristics. First, we estimate E½Tcf by
considering two factors: energy consumption and node
mobility. Let TcL and Tin be the lifetime and residence times Table 1 in order for us to conduct simulation experiments
of a cooperative node, respectively; then, the actual time (shown in Section 6.3) and estimate E½Ti heuristically.
that a cooperative node participates in network activities is In reality, typical batteries of current laptops can have
the minimum of its lifetime and residence time, i.e., much higher energy than Einit (e.g., the battery for IBM X41
Tcf ¼ minðTcL ; Tin Þ. Thus, E½Tcf can be upper bounded by provides 4.4 Ah with 14.4-V output, which supports the
energy consumption of all parts, including CPU and
E½Tcf ¼ E ½minðTcL ; Tin Þ minðTcL ; Tin Þ; ð35Þ display). In our work, Einit is referred to as the energy
consumed by wireless transceivers only. Consequently, Tin
where TcL is the mean of node lifetime and Tin is the
and TR are set to small values in accordance with the short
average residence time aforementioned. We can further
“lifetime.” The value for Ta is borrowed from the statistics
quantify TcL by
of worm infections (e.g., the Slammer worm can infect about
Einit 75,000 hosts within 30 minutes [33]). The values for PT x
TcL ; ð36Þ and PRx are actually derived from the per-packet energy

PT x þ ð1
ÞPRx
consumption model proposed in [34].
where PT and PR denote the average transmitting and Next, we obtain the TPM of our semi-Markov model as
receiving power, respectively. And
denotes the ratio follows by using the data collected from our simulations:
between the number of transmitted packets and that of
0 1
processed packets. To estimate E½Tsf , it is noticed that a 0 0:525 0:071 0:404
cooperative node becomes selfish if its residual energy is B 0:756 0 0:022 0:222 C
IP B
@ 0
C;
below Einit according to our scenario settings aforemen- 0 0 1 A
tioned. Further, considering that a selfish node does not 1 0 0 0
forward packets, if we let denote the ratio between the
number of forwarded packets and that of processed and then, the stationary distribution of the EMC is
packets, we can have the average lifetime of a selfish node
¼< 0:4524; 0:2375; 0:0373; 0:2728 > :
~
approximated by
Then, E½Tij can be calculated by using (35)-(39). Since pij
Einit
¼ TcL : are known already, E½Ti are calculable:
ð1 Þð
PT x þ ð1
ÞPRx Þ 1
E½Tc ¼ 142:2; E½Ts ¼ 45:9; E½Tm ¼ 51:7; E½Tf ¼ 60:
With a similar reasoning, we have E½Tsf upper bounded by
Last, we obtain the limiting probabilities Pi by using (9):

E½Tsf min TcL ; Tin : ð37Þ
1 Pc ¼ 0:6877; Ps ¼ 0:1167; Pm ¼ 0:0207; Pf ¼ 0:1750:
To estimate E½Tmf , recall that a node can be compromised
Remark 4. Although the accuracy of using the heuristic
at any time and become malicious after an average (attack)
period Ta ; thus, we can bound E½Tmf from above as method depends on the soundness of the heuristics
established (in (35)-(39), for example), the heuristic

TcL method provides us an approach to analyze the effect
E½Tmf min Ta ; Tin : ð38Þ of a specific dynamic factor such as node mobility on the
2
stochastic property of node behaviors. Since we have
Other expected transition times are approximated by proved that the network survivability also depends on
the behavior state distributions, the limiting probability
TcL
E½Tcm ¼ E½Tsm þ Ta ; plays an important role in bridging the gap between the
2 network survivability and any specific dynamic that
E½Tcs ð1 ÞTcL ; ð39Þ
directly affects the limiting probability. Therefore, the
Iinit semi-Markov node behavior model proposed in this
E½Tsc ; E½Tfc TR :
I paper not only provides us with a general mathematical
At last, E½Ti can be calculated by using (10) similarly. framework to describe node behaviors but also is
Now, we give an example to show how to calculate Pj applicable to evaluate the impact of a wide variety of
by using the heuristic estimation. First, all parameters random dynamics on the network survivability, via its
aforementioned are assigned with the values shown in state distributions.
TABLE 2
The Network Setup in Simulations
6.2 Simulation Setup

To evaluate the correctness of our theoretical analysis, we Fig. 4. Limiting probabilities.
conducted exhaustive simulations in the simulation tool ns2
(v2.28) and a series of numerical experiments in Matlab (v7). on the limiting probability. In particular, the cooperative
In simulations, the network area approximately represents probability Pc is of our concern due to its importance in
the center of a town. The number of nodes (network size N) network survivability.
is ranging from 100 to 900 to represent small and large
networks. The mobility model chosen is the Semi-Markov 6.3.1 Effect of Initial Energy
Smooth (SMS) model [35], which provides a uniform node In Fig. 5, the heuristic value of Pc is increased from 0.69 to
distribution and more realistic movement patterns. Unless 0.74 when the initial energy Einit is increased from 100 Ws
otherwise indicated, the speed is uniformly distributed to 200 Ws, which is consistent with the intuition that a
between 0 and 10 m/s to represent the movements of higher initial energy will increase the node lifetime.
pedestrians and cars. Constant Bit Rate (CBR) is chosen for Nevertheless, the increase is not significant, which is
traffic, and 100 sessions are constantly maintained in each partially due to the fact that the time spent in the selfish
traffic pattern; 100 sessions are constantly maintained to state may also be increased given that the selfish threshold
keep every node involved in networking. is fixed. Moreover, it is worthy of mentioning that Pm is
Moreover, in simulations, nodes change their behaviors almost doubled after the increase of Einit since the lifetime
according to the policies described in Section 6.1. For of a malicious node is actually prolonged. Thus, the impacts
cooperative nodes, AODV is used as the routing protocol, of energy are twofold, that is, increasing energy can make
while for misbehaving nodes, a modified version of AODV end users behave cooperatively for a longer time but may
was developed so that their behaviors do not comply with the also exaggerate the impact of malicious nodes on network
routing and forwarding rules defined in the standard. survivability.
Specifically, selfish nodes do not forward RREQ and
6.3.2 Effect of Node Mobility
RREP messages for others; malicious nodes forward
RREQ and RREP messages but drop data packets to be To evaluate the impact of node mobility on Pc , we conducted
forwarded. The results are averaged over multiple simulation simulations using two different average speeds, 20 m/s and
2 m/s, with 10 movement patterns corresponding to each of
rounds conducted with various random seeds. The simula-
them. The SMS mobility model used in our paper provides
tion time is set to 2,000 s so that the system can reach steady
the uniform node distribution, which eliminates the side
states. The default network parameters are listed in Table 2.
effect of some artifacts such as inhomogeneous node density
6.3 Limiting Probability Evaluation induced by the Random-waypoint model [36] such that the
effect of speed can be evaluated accurately. When the
To demonstrate the existence of limiting probabilities, all
parameters are set as the values in Table 1. We calculated
Pj ðj 2 SÞ every 10 s based on the cumulated statistics, by
using the empirical method introduced in Section 6.1, and
illustrated the results with respect to the simulation time in
Fig. 4. In the figure, we can see clearly that as more and
more statistics are used, the vibration of Pj keeps attenuat-
ing, and Pj finally reaches the limiting value after about
1,000 seconds. We also annotated heuristic values of Pj
(calculated in Section 6.1 already) in the figure (shown as
solid and dashed lines), from which we can see a good
match between the limiting probabilities and the heuristic
values. This observation confirms the existence of the
limiting probabilities and the soundness of our heuristics.
Next, we demonstrate how to use our model to
investigate the impact of different parameters, including
the initial energy Einit and node mobility (in terms of Tin ), Fig. 5. The effect of Einit on Pc .
Fig. 6. The effect of nodal mobility on Pc . Fig. 7. The effect of node cooperativeness on network survivability.
simulation area is bounded, we did not observe a substantial the node selfishness and Jellyfish attack. By adjusting the
difference in Pc for both average speed settings. The reason selfish threshold and attack time Ta , a series of Pc values
is quite simple: since all nodes are constrained within the ranging from 0.05 to 0.95 (roughly) were obtained by using
boundary, different speeds have no effect on the node the heuristic estimation. The analytical survivability (lower
residential time, which in turn do not affect Pi . However, in bound) was then calculated for k ¼ 1; 2; 3 by using (29) with
real networks, the boundary does often not exist, and nodes these Pc values. The simulation and analytic results are
can hardly be confined in a given area. To demonstrate the
shown in Fig. 7, where the curves with markers represent the
impact of node mobility in a real environment, we enlarged
network survivability measured from simulation data, and
the simulation area but still assigned a 1,000 m 1,000 m
square as the predefined network such that the churn due to the ones without markers are for analytical results. In this
movements can be detected. The simulation results are figure, it is obvious that the network survivability increases
shown in Fig. 6, in which we can see that the average speed when we decrease the connectivity requirement ðkÞ, which
affects Pc considerably, i.e., the higher the mobility is, the indicates that the stronger the connectivity a network has,
lower Pc is. To explain this phenomenon, notice the fact that the more survivable the network is in terms of its topology.
the faster a node moves, the sooner the node traverses the An interesting observation is that the survivability increases
boundary, yielding a smaller average residence time Tin . very fast from zero to one as Pc increases, for example, the
Consequently, Pc is decreased due to the decreased time survivability for k ¼ 2 is almost zero as Pc 0:4, while it
spent in the network. The heuristic values of Pc , annotated in jumps to almost one as Pc 0:7. This observation is actually
the figure, are calculated by varying Tin , which is simply in accordance with the so-called phase transition phenomen-
estimated by dividing the diagonal of the network by the on in (geometric) random graphs (see [27] and [20]) and
average speed. indicates that there exists a critical value of Pc for network
6.4 Network Survivability Evaluation survivability. Finally, we can see that the analytical results
In this section, we verify the correctness of our theoretical match with the simulation results with only minor deviation,
bounds on the network survivability. In simulations, the and especially, the deviation becomes almost invisible when
k-connected survivability is calculated by the ratio between the survivability is above 0.8. This confirms the tightness of
the number of k-connected topologies and that of all the asymptotic lower bound derived from our theoretical
topologies studied (around 1,000). Since detecting the analysis.
connectivity of a network requires extensive computing
6.4.2 The Effect of Node Failures
time, we only consider k up to three. In order to eliminate
the border effect described in Section 5.3, we used a To explain the effect of node failures on network
wraparound distance (i.e., toroidal distance [15]) so that survivability, we set both Ps and Pm as zero, by tuning
nodes at the border are considered as being close to nodes and Ta , to eliminate the impact of misbehaving nodes.
at the opposite border and they are allowed to have links. By adjusting initial energy Einit and recharging time TR ,
Further, only the lower bound given in (29) will be depicted we obtain Pf in the range of 0.0376 to 0.8177. Then, the
as the analytical approximation to the network survivability network survivability for k ¼ 1; 2; 3 is calculated against
because the upper bound (28) is quite loose compared to each of the Pf ðPc ¼ 1 Pf Þ values. The simulation and
the simulation results. In the simulation, all network analytical results are plotted in Fig. 8. In this figure, we
parameters are set to the default values given in Table 2. observed a similar “phase transition” phenomenon, that
Next, we explain our simulation results. is, the network survivability decreases very fast as Pf
increases, especially after a certain value. For example,
6.4.1 The Effect of Node Cooperativeness when Pf 0:5, the survivability for k ¼ 1 is almost zero,
To observe the effect of node cooperativeness clearly, we set which implies that the network is disconnected almost
the recovery time as zero so that the effect of node failures is surely, while an almost sure survivability is achievable
eliminated. We also set PB ¼ 0 so that Pc varies only due to only if Pf 0:3.
the fact that misbehaving nodes are still active in the network
layer so that they do not affect the density of active nodes a ,
which is, however, an important factor for network
survivability.
6.5 Impacts on Network Performance

To provide a complete picture of the negative effect of node
misbehaviors, we also evaluated the network performance
when misbehaving nodes are present by simulations, where
misbehaving nodes simply drop all data packets to be
forwarded once paths are established. This is a special case of
the traditional Jellyfish attack and is actually called as the
“Blackhole” attack in [19] (different from the Blackhole
Fig. 8. The effect of node failures on network survivability. concept in our work). It was pointed out that the perfor-
mance impact caused by this particular misbehavior is
nearly the same as that caused by traditional Jellyfish attacks
that manipulate the delay, reordering, and selective drop-
ping. Thus, we can use CBR (over UDP) to obtain a similar
performance evaluation as we use TCP for traditional
Jellyfish attacks aforementioned, as conducted in [19]. In
simulations, the following metrics are considered in the
evaluation: normalized goodput, average end-to-end delay,
and average hop count, with all network parameters set to
the default values in Table 2. The simulation results are
shown in Fig. 10.
In Fig. 10a, the normalized goodputs are shown to
decrease significantly when more misbehaving nodes
perform abnormal routing operations. This impact is
Fig. 9. The effect of selfish and malicious nodes on network survivability. particularly severe to the well-connected network with
N ¼ 500 nodes. The reason for the drastic degradation on
6.4.3 The Effect of Node Misbehaviors goodput is partially due to the fact of substantial network
partitioning effect caused by node misbehaviors, corre-
In a similar way, we eliminated the effect of node failures in
sponding to the decreased survivability. In particular, the
order to study the impact of node misbehaviors only. The
goodput for the network with N ¼ 100 nodes is quite low
simulation and analytical results are depicted in Fig. 9.
due to the fact that the network is actually disconnected
Similar to the plots in Fig. 8, the curves in Fig. 9 also indicate
all the time. An interesting observation is that this node
that the survivability decreases when more and more misbehavior can shorten end-to-end delays significantly,
misbehaving nodes are present, which is consistent with especially for dense networks (e.g., N ¼ 900), as shown in
our intuition and the fact of decreased Pc . Nevertheless, Fig. 10b. However, this plausible “improvement” is at the
compared with the results shown in Fig. 8, we observed that cost of suffocating the traffic on long paths, which is
the change of survivability due to node misbehaviors is less explained by the results in Fig. 10c. In fact, the decrease
significant than that due to node failures, especially for lower of average hop count is not because shorter paths can be
connectivity requirement. For example, the survivability for found; instead, it captures the effect of network partition-
k ¼ 1 does not decrease considerably until Ps þ Pm 0:5, ing and survivability downgrading.
and it keeps positive till Ps þ Pm 0:7. As we have Nevertheless, although a low survivability results in a
mentioned in Section 5.3, this observation is accordant with low performance, we cannot conclude a similar implication
Fig. 10. Impacts of misbehaving nodes on network performance. (a) Normalized goodput. (b) End-to-end delay. (c) Average hop count.
in the opposite direction. Indeed, providing a theoretical the survivability of wireless ad hoc networks in the
analysis on the impact of node behaviors on network presence of both node misbehaviors and random failures.
performance is still an open and interesting problem, which
will be our future research topic.
8 CONCLUSION
In this paper, we developed an analytic framework to
7 RELATED WORK study the impact of node misbehaviors and failures
As aforementioned in Section 2.2, although network on network survivability, which is defined as the probabil-
survivability has been defined from different perspectives istic k-connectivity of the network induced by active nodes.
and analyzed extensively for wired and infrastructure We first classified node behaviors and proposed a novel
wireless networks, only a few survivability studies were semi-Markov behavior model to characterize the behavior
made for wireless ad hoc networks. Chen et al. presented a transitions. With the limiting distribution obtained from the
quantitative approach to evaluate the system survivability model, we next studied the node isolation problem and
performance in [6] and introduced ELF as the survivability derived the probabilistic connectivity of individual nodes.
measure for wireless ad hoc networks. To obtain ELF, the Finally, we derived the closed-form approximation of the
authors assumed a Markovian property for the network and network survivability by using an (loose) upper bound and
conducted an end-to-end availability analysis by solving a (tight) lower bound, which turns out to be a function of the
set of CTMC models. This work considered both node network properties (network size N, transmission range r,
failure durations and their impacts on the network. Never- and initial density ) and node behavior distributions.
theless, based on our analysis, the Markovian assumption In conclusion, the impact of node behaviors (failures) on
may not hold in wireless ad hoc networks in general. network survivability can be evaluated quantitatively from
Further, an assumption of the Markov availability model is our analytical result (Theorem 2), which can be further used as
that for any pair of nodes, other ðN 2Þ, nodes may act as a guideline to design or deploy a survivable ad hoc network
routers, which is, however, not true due to the limitation of given a predefined survivability preference. Further, the
node degrees. semi-Markov node behavior model can be used as a bridge
In another experimental study [8], Paul et al. analyzed between any dynamic factors such as node mobility or attack
the survivability of wireless ad hoc networks with respect to intensity (ratio) and network survivability, as long as the
the dynamic topology changes. In this study, the network factor affects state distributions explicitly. Last but not least,
survivability was perceived by a number of metrics such as it is surprising that node misbehaviors may “improve”
average connectivity efficiency, average network stability, network performance in terms of end-to-end delays in some
and service efficiency. Nevertheless, this work did not scenarios; however, this plausible performance improve-
provide any theoretical analysis to all survivability mea- ment sacrifices the survivability of wireless ad hoc networks
sures aforementioned and did not take any failure model because of increased node isolations.
into consideration. Similarly, although network connectiv-
ity was used by a few of other survivability studies such as ACKNOWLEDGMENTS
[9] and [10], no analysis has ever been conducted to reveal
This work is supported in part by the US National Science
the impact of failures on the topological survivability.
Foundation (NSF) under Award CAREER CNS-0546289
Contrary to the limited theoretical result in the current
survivability analysis, there have been abundant theories and the Defense Threat Reduction Agency (DTRA) under
available from the state-of-the-art connectivity studies. For Award HDTRA-1-08-1-0024. Parts of this paper appeared in
example, in [15], the connectivity of wireless multihop the Proceedings of the IEEE International Conference on
networks was studied thoroughly, and a tight bound was Communications (ICC ’06) [1].
given to the problem of finding ðr; nÞ pairs that achieve an
almost surely connected network, where r and n denote the REFERENCES
transmission range and the number of nodes, respectively.
[1] F. Xing and W. Wang, “Modeling and Analysis of Connectivity in
An earlier work [14] even provided a closed-form approx- Mobile Ad Hoc Networks with Misbehaving Nodes,” Proc. IEEE
imation of probabilistic k-connectivity, which can be Int’l Conf. Comm. (ICC ’06), pp. 1879-1884, June 2006.
deduced from our main result (29) by assuming that all [2] R. Ellison, D. Fisher, R. Linger, H. Lipson, T. Longstaff, and
N. Mead, “Survival Network Systems: An Emerging Discipline,”
nodes are cooperative. Nevertheless, node degree was
Technical Report CMU/SEI-97-TR-013, SEI, CMU, http://www.
considered as the only criteria to decide node isolation, and cert.org/research/97tr013.pdf, 1997.
the scenario where nodes might be isolated by misbehaving [3] “Telecom Glossary 2000,” Technical Report ANS T1.523-2001,
neighbors has never been considered in previous connectiv- Institute for Telecomm. Services, NTIA, DOC, http://www.atis.
org/tg2k/, Feb. 2001.
ity studies. [4] J.C. Knight and K.J. Sullivan, “On the Definition of Survivability,”
In summary, we can see that previous works either Technical Report CS-TR-33-00, Dept. Computer Science, Univ. of
concentrated on the impact of node misbehaviors or DoS Virginia, Jan. 2000.
attacks on network performance but with no consideration [5] A.P. Snow, U. Varshney, and A.D. Malloy, “Reliability and
Survivability of Wireless and Mobile Networks,” IEEE Computer
to topology survivability [17], [18], [19] or focused on the Magazine, vol. 33, no. 7, pp. 449-454, July 2000.
survivability of wireless networks without considering the [6] D. Chen, S. Garg, and K.S. Trivedi, “Network Survivability
unique feature of ad hoc networks and the potential impact Performance Evaluation: A Quantitative Approach with Applica-
tions in Wireless Ad-hoc Networks,” Proc. ACM Int’l Workshop
of all kinds of node behaviors. We hope that our paper is Modeling, Analysis, and Simulation of Wireless and Mobile Systems
the first unified study to provide a theoretical approach for (MSWiM ’02), pp. 61-68, Sept. 2002.
[7] E. Mannie and D. Papadimitriou., eds., Recovery (Protection and [34] L.M. Feeney and M. Nilsson, “Investigating the Energy Con-
Restoration) Terminology for Generalized Multi-Protocol Label Switch- sumption of a Wireless Network Interface in An Ad Hoc
ing (GMPLS), IETF RFC 4427, http://www.ietf.org/rfc/ Networking Environment,” Proc. IEEE INFOCOM ’01, vol. 3,
rfc4427.txt, Mar. 2006. pp. 1548-1557, Apr. 2001.
[8] K. Paul, R.R. Choudhuri, and S. Bandyopadhyay, “Survivability [35] M. Zhao and W. Wang, “A Unified Mobility Model for Analysis
Analysis of Ad Hoc Wireless Network Architecture,” Proc. IFIP- and Simulation of Mobile Wireless Networks,” ACM-Springer
TC6/European Commission Int’l Workshop Mobile and Wireless Comm. Wireless Networks, Sept. 2007.
Networks, C.G. Omidyar., ed., pp. 31-46, 2000. [36] N. Sadagopan, F. Bai, B. Krishnamachari, and A. Helmy, “PATHS:
[9] D. Goyal and J.J. Caffery, “Partitioning Avoidance in Mobile Analysis of PATH Duration Statistics and their Impact on Reactive
Ad Hoc Networks Using Network Survivability Concepts,” MANET Routing Protocols,” Proc. ACM MobiHoc ’03, June 2003.
Proc. Seventh Int’l Symp. Computers and Comm. (ISCC), May
2002. Fei Xing received the BS and MS degrees from
[10] H. Kawahigashi, Y. Terashima, N. Miyauchi, and T. Nakakawaji, Xian Jiaotong University, Xian, China, in 1999
“Designing Fault Tolerant Ad Hoc Networks,” Proc. IEEE/AFCEA and 2002 respectively, and the PhD degree from
Military Comm. Conf. (MILCOM), 2005. North Carolina State University, Raleigh, in
[11] J.P. Sterbenz, R. Krishnan et al., “Survivable Mobile Wireless 2009. His research interests include resilient
Networks: Issues, Challenges, and Research Directions,” Proc. wireless network design, mobile ad hoc net-
ACM Workshop Wireless Security (WiSe ’02), pp. 31-40, Sept. works, and wireless communication systems.
2002. Before joining the doctoral program, he worked
[12] X.-Y. Li, P.-J. Wan, Y. Wang, and C.-W. Yi, “Fault Tolerant as an engineer for FujiXerox Japan, Huawei
Deployment and Topology Control in Wireless Networks,” Proc. Technologies, and Infineon Technologies, se-
ACM MobiHoc ’03, pp. 117-128, Jan. 2003. quentially. He is currently with Cisco Systems. He is a student member
[13] F. Xue and P. Kumar, “The Number of Neighbors Needed for of the IEEE.
Connectivity of Wireless Networks,” Kluwer Wireless Networks,
vol. 10, no. 2, pp. 169-181, Mar. 2004. Wenye Wang received the BS and MS degrees
[14] C. Bettstetter, “On the Minimum Node Degree and Con- from the Beijing University of Posts and Tele-
nectivity of a Wireless Multihop Network,” Proc. ACM communications, Beijing, in 1986 and 1991,
MobiHoc ’02, pp. 80-91, June 2002. respectively, and the MSEE and PhD degrees
[15] C. Bettstetter, “On the Connectivity of Ad Hoc Networks,” from the Georgia Institute of Technology,
Computer J., special issue on mobile and pervasive computing, Atlanta, in 1999 and 2002, respectively. She is
vol. 47, no. 4, pp. 432-447, 2004. an associate professor with the Department of
[16] P.-J. Wan and C.-W. Yi, “Asymptotic Critical Transmission Electrical and Computer Engineering, North
Radius and Critical Neighbor Number for k-Connectivity in Carolina State University, Raleigh. Her research
Wireless Ad Hoc Networks,” Proc. ACM MobiHoc, 2004. interests are in mobile and secure computing,
network topology and architecture, fault-tolerant computing in single-hop
[17] S. Marti, T.J. Giuli, K. Lai, and M. Baker, “Mitigating Routing
and multihop networks. Since 2003, she has served on many program
Misbehavior in Mobile Ad hoc Networks,” Proc. ACM
committees of several conferences, including IEEE INFOCOM, ICC,
MobiCom ’00, pp. 255-265, 2000.
ICCCN, and GLOBECOM. She was a recipient of the US National
[18] V. Srinivasan, P. Nuggehalli, C.F. Chiasserini, and R.R. Rao, Science Foundation CAREER Award in 2006. She has been a member
“Cooperation in Wireless Ad Hoc Networks,” Proc. IEEE of the ACM since 2002 and is also a member of the IEEE.
INFOCOM ’03, pp. 808-817, Mar. 2003.
[19] I. Aad, J.-P. Hubaux, and E.W. Knightly, “Denial of Service . For more information on this or any other computing topic,
Resilience in Ad Hoc Networks,” Proc. ACM MobiCom, 2004. please visit our Digital Library at www.computer.org/publications/dlib.
[20] M. Penrose, Random Geometric Graphs. Oxford Univ. Press,
2003.
[21] L. Buttyan and J.-P. Hubaux, “Stimulating Cooperation in Self-
Organizing Mobile Ad Hoc Networks,” Mobile Networks and
Applications, vol. 8, no. 5, pp. 579-592, Oct. 2003.
[22] D. Miorandi and E. AltmanA, “Coverage and Connectivity of
Ad Hoc Networks in Presence of Channel Randomness,” Proc.
IEEE INFOCOM ’05, pp. 491-502, Mar. 2005.
[23] J. Medhi, Stochastic Processes. John Wiley & Sons, 1994.
[24] G. Corradi, J. Janssen, and R. Manca, “Numerical Treatment of
Homogeneous Semi-Markov Processes in Transient Case—A
Straightforward Approach,” Methodology and Computing in Applied
Probability, vol. 6, pp. 233-246, 2004.
[25] J.-K. Lee and J.C. Hou, “Modeling Steady-State and Transient
Behaviors of User Mobility: Formulation, Analysis, and Applica-
tion,” Proc. ACM MobiHoc ’06, pp. 85-96, May 2006.
[26] D. Heyman and M. Sobel, Stochastic Models in Operations Research.
McGraw-Hill, 1982.
[27] B. Bollobas, Modern Graph Theory. Springer, 1998.
[28] B. Bollobas, Random Graphs. Academic Press, 1985.
[29] P. Santi, Topology Control in Wireless Ad Hoc and Sensor Networks.
John Wiley & Sons, 2006.
[30] M.D. Penrose, “On k-Connectivity for a Geometric Random
Graph,” Random Structures and Algorithms, vol. 15, no. 2,
pp. 145-164, 1999.
[31] R. Hekmat, Ad-Hoc Networks: Fundamental Properties and Network
Topologies, first ed. Springer, 2006.
[32] Z. Nikoloski1, N. Deo, and L. Kucera, “Degree-Correlation of a
Scale-Free Random Graph Process,” Proc. European Conf. Combi-
natorics, Graph Theory and Applications (EuroComb ’05), pp. 239-244,
2005.
[33] D. Moore, V. Paxson, S. Savage, C. Shannon, S. Staniford, and
N. Weaver, “Inside the Slammer Worm,” IEEE Security and
Privacy, vol. 1, no. 4, pp. 33-39, July/Aug. 2003.

On The Survivability of Wireless Ad Hoc Networks With Node Misbehaviors and Failures

Uploaded by

Copyright:

Available Formats

On The Survivability of Wireless Ad Hoc Networks With Node Misbehaviors and Failures

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

On The Survivability of Wireless Ad Hoc Networks With Node Misbehaviors and Failures

Uploaded by

Copyright:

Available Formats

284 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 7, NO.

On the Survivability of Wireless Ad Hoc

N ETWORK survivability is an essential aspect of reliable

where xi 2 S for 0 i n þ 1. From (2), fXn ; n ¼ 0;

6.1.2 Heuristic Estimation TABLE 1

6.2 Simulation Setup

6.5 Impacts on Network Performance

You might also like