JOURNAL OF L
A
TEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007 1
A Graphtheoretic Frameworkfor Identifying Trigger Nodes againstProbabilistic Reactive Jamming Attacks
Ying Xuan, Yilin Shen, Incheol Shin, My T. Thai
Abstract
—During the last decade,
Reactive
Jamming Attack has emerged as a greatest security threat to wireless sensor networks,due to its mass destruction to legitimate sensor communications and difﬁculty to be disclosed and defended. Considering thespeciﬁc characteristics of reactive jammer nodes, a new scheme to deactivate them by efﬁciently identifying all
trigger nodes
, whosetransmissions invoke the jammer nodes, has been proposed and developed. Such a trigger identiﬁcation procedure could serve as aleverage subroutine for a jammingresistent routing scheme and exhibit great potentials in enhancing the defense efﬁciency. By modelingthisprocedureasagraphoptimizationproblem,inthispaper,ontheonehand,weemployedanadvanced
randomizederrortolerantnon adaptive group testing
technique and a classic
cliqueindependent set
problem to further speed up the identiﬁcation process, comparedto our previous work. On the other hand, by investigating two sophisticated jamming behavior models, we proposed an efﬁcient algorithmwhich limits the identiﬁcation false rates to desirable low levels. The theoretical analysis and simulation results illustrate the robustnessand efﬁciency of the proposed solution.
Index Terms
—Trigger Identiﬁcation, CliqueIndependent Set, Errortolerant Nonadaptive Group Testing, Graph Theory, Optimization,NPHardness.
!
1 I
NTRODUCTION
S
INCE
the last decade, the security of wireless sensornetworks (WSNs) has attracted numerous attentions, dueto its wide applications in various monitoring systems andinvulnerability toward sophisticated wireless attacks. Amongthese attacks, jamming attack where a jammer node disruptsthe message delivery of its neighboring sensor nodes withinterference signals, has become the most critical threat toWSNs. Thanks to the efforts of researchers toward this issue,as summarized in [11], various efﬁcient defense strategies havebeen proposed and developed. However, a reactive variant of this attack, where jammer nodes stay quite until an ongoinglegitimate transmission (even has a single bit) is sensed overthe channel, emerged recently and called for stronger defendingsystem and more efﬁcient detection schemes.Existing countermeasures against Reactive Jamming attacksconsist of jamming (signal) detection and jamming mitigation.On the one hand, detection of interference signals from jammernodes is nontrivial due to the discrimination between normalnoises and adversarial signals over unstable wireless channels.Numerous attempts to this end monitored critical communica
•
Y. Xuan, Y. Shen, I. Shin and My T. Thai are with the Department of Computer Information Science and Engineering. Email:
{
yxuan, yshen, ishin, mythai
}
@cise.uﬂ.eduThis is an extended version of “Y. Xuan, Y. Shen, I. Shin, M. T. Thai, ”OnTrigger Detection Against Reactive Jamming Attacks: A CliqueIndependent Set Based Approach”, IPCCC, Phoenix, Arizona, 2009.”
tion related objects, such as
Receiver Signal Strength
(RSS),
Carrier Sensing Time
(CST),
Packet Delivery Ratio
(PDR),compared the results with speciﬁc thresholds, which wereestablished from basic statistical methods and multimodalstrategies [8][11]. By such schemes, jamming signals couldbe discovered, however, how to locate and catch the jammernodes based on these signals is much more complicated andhas not been settled. On the other hand, in order to mitigatethese attacks, two strategies were adopted at sensor nodes toescape from the detected interferences, namely, channel surﬁngand spatial retreats [11]. The former one employs frequencyhopping techniques at both communication ends [5][7][9], inwhich case jammer nodes are unable to ﬁnd the current channelthat is used for the communication, so that the attack efﬁciencyis greatly decreased. The latter one requires sensor nodes toretreat from the possible jammed areas, then no sensor nodeswill be effected by the jamming signals [10][12]. However,owing to the limited power and spectral diversity [8] of wirelesssensors, these mitigation schemes are inefﬁcient due to theirconsiderable computation and communication overheads.Instead of discovering the jammed areas, which may beinaccurate and unnecessarily large, we proposed a new solutionto mitigate the attacks by identifying the
trigger nodes
in [6],whose transmissions invoke the jammer nodes, and preventingthese trigger nodes from transmitting messages. Speciﬁcally,we provided a novel jammingresistent routing scheme withregulating all identiﬁed trigger nodes as terminals, thereforeno messages will be transmitted from the trigger nodes and
JOURNAL OF L
A
TEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007 2
all jammer nodes will stay quiet. The motivation of studyingthis trigger identiﬁcation problem is not limited in this reactive jamming scenario, but to provide a solution framework to themitigations against the reactive variant of a general scope of attacks.Since the performance of the trigger identiﬁcation is critical for the routing scheme and other applications that makebeneﬁt from it, in this paper, we develop a solution for realsophisticated attack scenarios. Speciﬁcally, as many attackersplay tricks to evade detections, the feedbacks of jammer nodestoward sensed message transmissions can be nondeterministicor along with randomized time delays. To handle these unsurefactors, we introduce a novel
randomized errortolerant grouptesting scheme
, which is combined with a cliqueindependentset model, and speeds up the identiﬁcation procedure with lowerror rates under unreliable enviroments. The basic idea of oursolution is to partition the victim nodes (which are interferedby jamming signals) into multiple
testing teams
, and thenconduct
group testing
based on the constructed randomized
(
d,z
)
disjunct matrix, by letting each victim node broadcasttest messages simultaneously and some
leader
nodes gatherthe feedbacks (interference signals) from the jammers. Bygenerating
test outcomes
from these gathered feedbacks, allthe trigger nodes are identiﬁed via a prompt decoding process.Compared with our previous work [6], more sophisticated jammer behaviors are considered and handled in this paper bythe new group testing scheme, with lower time and communication complexity, as well as accuracy guarantees. Moreover,we model the partitioning phase of victim nodes as a
cliqueindependent set
problem, whose NPHardness on UDG (unitdisk graph) is shown.In the remainder of this paper, we ﬁrst present the problemdeﬁnition in Section 2, where the network model, victimmodel and attacker models are included. Then we introducetwo kernel techniques for our scheme,
cliqueindependent set
and
randomized errortolerant nonadaptive group testing
in Section 3. The core of this paper:
trigger identiﬁcation procedure
and its errortolerant extension toward sophisticated jammer behaviors are presented respectively in Section 4 and5. A series of simulation results for evaluating the systemperformance and validating the theoretical results are includedin Section 6. We also present some related works in Section 7and summarize the whole paper in Section 8.
2 P
ROBLEM
M
ODELS AND
D
EFINITION
2.1 Network Model
We consider a wireless sensor network consisting of
n
sensornodes and one base station (larger networks with multiple basestations can be split into small ones to satisfy the model).Each sensor node has a uniform transmission radius
r
and isequipped with
m
radios for in total
k
channels throughout thenetwork, where
k > m
. The network can abstracted as a
unit disk graph
(UDG)
G
= (
V,E
)
, where any node pair
i,j
isconnected iff the Euclidean distance between
i,j
:
δ
(
i,j
)
≤
r
.
2.2 Victim Model
Victim nodes
refer to those sensor nodes whose transmissionsare disturbed by jamming signals, i.e., node
v
is a victim node
iff
δ
(
J,v
)
≤
R
for some
activated
jammer
J
. In this paper,we assume that each sensor can identify received jammingsignals and justify whether itself is a victim node. Furthermore,the results of these selfidentiﬁcations are reported to thebase station by means of the existing message forwardingschemes periodically, therefore the set of victim nodes ismaintained at the base station. Since the detection of jammingsignals have been well developed with multimodal statisticalmethods, the above assumptions are feasible even in unreliableenvironments.As a subset of the victim nodes,
trigger nodes
refer toa subset of victim nodes, whose transmissions activate the jammer nodes. In another word, node
v
is a trigger node
iff
δ
(
J,v
)
≤
r
for some activated jammer
J
. Therefore theproblem studied in this paper is to identify all the trigger nodesfrom a given set of victim nodes.
2.3 Attacker Model
We consider both a basic attacker model and several advancedattacker models in this paper. In the next sections, we willﬁrst illustrate our framework solution toward the basic attackermodel, and then validate its performance toward multipleadvanced attacker models theoretically and experimentally.
2.3.1 Basic Attacker Model
The basic attacker model is deﬁned as follows: there existsat most
J
≪
n
reactive jammer nodes in the network,whose transmission radiuses are
R
=
αr
with
α >
1
.These jammer nodes keep idle until they sense any ongoinglegitimate transmissions and broadcast interference signals to jam all the sensors in distance
R
on this speciﬁc channel. Themaximum damages caused by the jammer nodes are limitedto the interferences toward speciﬁc sensor nodes on speciﬁctransmission channels for a short period, instead of longtermdisabling the sensors. The motivation behind this assumptionarises from the basic goal of reactive jamming: disrupt themessage delivery with minimum energy cost. As soon as thesensors detect any jamming signals, the transmissions will beterminated, or continue on some other channels. Thus it isunnecessary for the jammer nodes to keep sending interferencesignals on this channel for a long time, or either disrupt allthe channels with large energy overheads as an active jammerdoes. Moreover, from the standpoint of the attacker, it willbe a waste to deploy two jammer nodes too close to eachother, thus we assume that for any two jammer nodes
J
1
and
J
2
,
δ
(
J
1
,J
2
)
≥
2
R
−
R
′
with a small overlap
R
′
such that
R
′
≤
R
−
r
(see Fig. 3 in the next section).
2.3.2 Advanced Attacker Models
Considering possible adjustments at the jammer nodes toevade the detection, we take into account two probabilistic
JOURNAL OF L
A
TEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007 3
attacker models:
probabilistic attack
and
variant response timedelay
. In the ﬁrst one, the jammer responds each sensedtransmission with a probability
η
independently. Practically,
η
is approaching
1
, to guarantee the attack efﬁciency. However,in order to validate the accuracy of our solution toward extremecases, we also consider small
η
in the theoretical analysis andsimulations. In the other model, the jammer delays each of its jamming signals with an independently randomized timeinterval. Similarly, too large delays do not make sense forpractical attacks, but our solution is also satisﬁable under theseextreme cases.It is evident that most tricks in reactive jamming attack can be abstracted into either of these two models. Therefore,showing the efﬁciency of our identiﬁcation toward such modelssufﬁces validating its applicability to practical defense systemsand unreliable WSN environments.
3 T
WO
K
ERNEL
T
ECHNIQUES
This section includes two advanced techniques which beneﬁtour identiﬁcation procedure. We ﬁrst provide the NPhardnessproof of the
CliqueIndependent Set
problem along with a simple approximation algorithm, then introduce the
randomized errortolerant group testing
by providing our novel design forrandomized
(
d,z
)
disjunct matrix.
3.1 CliqueIndependent Set
CliquesIndependent Set is the problem to ﬁnd a set of maximum number of pairwise vertexdisjoint maximal cliques,which is referred as a
maximum cliqueindependent set
(MCIS)[4]. Since this problem serves as the abstracted model of the
grouping
phase of our identiﬁcation, its hardness is of greatinterest in this scope. To our best knowledge, it has alreadybeen proved to be NPhard for cocomparability, planar, lineand total graphs, however its hardness on UDG is still an openissue.
3.1.1 NPhardness
In this section, we prove the NPhardness of this problemon UDG via a polynomialtime reduction from the
Maximum Independent Set
problem on planar graph with maximum nodedegree 3 to it.From [20], the
Maximum Independent Set
problem is NPhard on planar graph with maximum degree 3, and from [21],any planar graph
G
with maximum degree 4 can be embeddedin the plane using
O
(

V

2
)
area units such that its vertices areat integer coordinates and its edges consist of line segments of the form
x
=
i
or
y
=
j
, for any integers
i
and
j
.
Theorem 3.1: CliqueIndependent Set
problem is NPhardon Unit Disk Graph.
Proof:
Given an instance
G
′
= (
V
′
,E
′
)
of such a
MIS
problem, whose optimal value is denoted as
MIS
(
G
′
)
, weconstruct an instance
G
= (
V,E
)
of the
CIS
problem asfollows:
•
Embed
G
′
in the plane in the way mentioned above [21].
•
For each node
v
i
∈
V
′
, attach two new nodes
v
i
1
and
v
i
2
to it and form a triangle
N
i
=
{
v
i
1
,v
i
2
,v
i
3
}
, where eachedge of this triangle
N
i
is of a unit length
r
=
√
33
.
•
Since each nodes
v
i
is incident to at most three edges,for all edges
(
v
i
,u
)
,
···
,
(
v
i
,v
)
, move their endpoint from
v
i
to different
v
ij
s, e.g.,
(
v
1
,u
)
changes to
(
v
11
,u
)
and
(
v
1
,v
)
to
(
v
12
,v
)
. Afterwards, for each of such edges
e
= (
u,v
)
, assume that it is of length
t
, we divide itinto
t
pieces and replace each piece with a concatenationof 2 triangles (not necessarily equilateral), as shown inFig. 1(b). Therefore, any edge
e
ij
= (
v
i
,v
j
)
∈
E
′
of length

e
ij

becomes a concatenation of
2

e
ij

3cliques,denoted as
{
c
1
,
1
ij
,c
1
,
2
ij
,c
2
,
1
ij
,
···
c

e
ij

,
1
ij
,c

e
ij

,
2
ij
}
. Because of the triangles
N
i
s, the two triangles at each corner of Fig.1(b) may need slight stenches, which can be done inpolynomial time.
•
The resulting graph
G
is then a unit disk graph with radius
r
=
√
33
.
9 9
V1V3V4V2
(a) Instance
G
′
= (
V
′
,E
′
)
of MISproblem on planar graph with maximumdegree 3
N1N3N2 N4
(b) Instance
G
= (
V,E
)
with radius
√
33
of CliqueIndependent Set problem on UDG
Fig. 1. Polynomial Time Reduction
The reduction is as follows:(
⇒
): if
G
′
has a maximum independent set
M
, for each
u
i
∈
M
, we choose cliques of two kinds in the correspondinginstance
G
: (1) the clique
N
i
at
u
i
; (2) for each incident edge
e
ij
= (
u
i
,u
j
)
, choose cliques
{
c
1
,
2
ij
,c
2
,
2
ij
,c
3
,
2
ij
,
···
,c

e
ij

,
2
ij
}
.Since the clique
N
j
at
u
j
shares a vertex with
c

e
ij

,
2
ij
, it cannotbe selected. For any edge
e
jk
= (
u
j
,u
k
)
where
u
j
/
∈
M
and
u
k
/
∈
M
, choose cliques
{
c
1
,
2
jk
,c
2
,
2
jk
,
···
c

e
jk

,
2
jk
}
. It is easy to
JOURNAL OF L
A
TEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007 4
verify that all the cliques selected are vertexdisjoint from eachother.Assume that after embedding
G
′
into the plane, each node
v
i
∈
V
′
has coordinate
(
x
i
,y
i
)
, then edge length

e
ij

=
∥
v
i
,v
j
∥
1
=

x
i
−
x
j

+

y
i
−
y
j

. Therefore if we have anindependent set of size

M

=
k
for
G
′
, we then have a cliqueindependent set of size
k
′
=
k
+
∑
(
i,j
)
∈
E
′

e
ij

.(
⇐
): if
G
has a clique independent set of size
k
′
, since thelengths of the embedded edges are constant, then
G
′
hasexactly an independent set of size
k
=
k
′
−
∑
(
i,j
)
∈
E
′

e
ij

.The proof is complete.
3.1.2 Algorithms
There have been numerous polynomial exact algorithms forsolving this problem on graphs with speciﬁc topology, e.g.,Helly circulararc graph and strongly chordal graph [4], butnone of these algorithms gives the solution on UDG. In thispaper, we employ the
scanning disk approach
in [3] to ﬁnd allmaximal cliques on UDG, and then ﬁnd all the
MCIS
usinga greedy algorithm. In fact, by abstracting this problem as a
Set Packing
problem, we can obtain a
√
n
approximation algorithm, however, it exhibits worse performance than the greedyalgorithm proposed in our trigger identiﬁcation procedure.
3.2 Errortolerant Randomized NonAdaptive GroupTesting
Group Testing was proposed since WWII to speed up theidentiﬁcation of affected blood samples from a large samplepopulation. This scheme has been developed with a completetheoretical system and widely applied to medical testing andmolecular biology during the past several decades [1]. Noticethat the nature of our work is to identify all triggers out of alarge pool of victim nodes, so this technique intuitively matchesour problem.
3.3 Traditional Nonadaptive Group Testing
The key idea of group testing is to test items in multipledesignated groups, instead of testing them one by one. Thetraditional method of grouping items is based on a designated
0

1
matrix
M
t
×
n
where the matrix rows represent the testinggroup and each column refers to an item, as Fig. 2 shows.
M
[
i,j
] = 1
implies that the
j
th
item appears in the
i
th
testinggroup, and
0
otherwise. Therefore, the number of rows of thematrix denotes the number of groups tested in parallel and eachentry of the result vector
V
refers to the test outcome of thecorresponding group (row), where
1
denotes positive outcomeand
0
denotes negative outcome.Given that there are at most
d < n
positive items amongin total
n
ones, all the
d
positive items can be efﬁciently andcorrectly identiﬁed on the condition that the testing matrix
M
is
d
disjunct: any single column is not
contained
by the unionof any other
d
columns. Owing to this property, each negativeitem will appear in at least one row (group) where all the
M
=
0 0 0 0 1 1 1 10 0 1 1 0 0 1 10 1 0 1 0 1 0 11 1 1 1 0 0 0 01 1 0 0 1 1 0 01 0 1 0 1 0 1 0
testing
=
⇒
V
=
001111
Fig.2. Binarytestingmatrix
M
andtestingoutcomevector
V
. Assumed that item
1
(
1
st
column) and item
2
(
2
nd
column) are positive, then only the ﬁrst two groups returnnegativeoutcomes,becausetheydonotcontainthesetwopositive items. On the contrary, all the other four groupsreturn positive outcomes.
positive items do not show up, therefore,
by ﬁltering all theitems appearing in groups with negative outcomes, all the left ones are positive
. Although providing such simple decodingmethod,
d
disjunct matrix is nontrivial to construct [1][2]which may involve with complicated computations with highoverhead, e.g., calculation of irreducible polynomials on GaloisField. In order to alleviate this testing overhead, we advancedthe deterministic
d
disjunct matrix used in [6] to randomizederrortolerant
d
disjunct matrix, i.e., a matrix with less rowsbut remains
d
disjunct w.h.p. Moreover, by introducing thismatrix, our identiﬁcation is able to handle test errors undersophisticated jamming environments.
3.4 Errortolerant Randomized Designs
In order to handle errors in the testing outcomes, the
errortolerant nonadaptive
group testing has been developed using
(
d,z
)
disjunct matrix, where in any
d
+1
columns, each columnhas
1
in at least
z
rows where all the other
d
columns are
0
.Therefore, a
(
d,
1)
disjunct matrix is exactly
d
disjunct. Byuse of
(
d,z
)
disjunct matrix, we can still correctly identify
d
positive items, even in the presence of at most
z
−
1
test errors.A prompt decoding scheme by differentiating positive andnegative items based on their number of appearances in groupswith negative outcomes is summarized in [1]: considering anysingle positive item
i
and negative item
j
. Suppose there are
c
negative groups containing
i
, then these
c
groups (tests)have errors, hence there are at most
z
−
1
−
c
other groupsturning negative outcomes to positive outcomes. Due to thedeﬁnition of
(
d,z
)
disjunct matrix, column
j
appears in atleast
z
negative groups where none of the
d
positive itemsexist, so even
z
−
1
−
c
of these groups are turned into positiveones, the number of negative groups containing
j
is at least
z
−
(
z
−
1
−
c
) =
c
+ 1
> c
. It is evident that by sorting allthe suspected items by their number of appearances in negativegroups, those
d
items with smallest number of appearances arepositive.In the literature, one the one hand, numerous deterministicdesigns for
(
d,z
)
disjunct matrix have been provided [1],
JOURNAL OF L
A
TEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007 5
however, these constructions often suffer from high computational complexity, thus are not efﬁcient for practical useand distributed implementation. On the other hand, to ourbest knowledge, the only randomized construction for
(
d,z
)
disjunct matrix dues to Cheng’s work via
q
nary matrix [19],which results in a
(
d,z
)
disjunct matrix of size
t
1
×
n
withprobability
p
′
, where
t
1
= 4
.
28
d
2
log21
−
p
′
+ 4
.
28
d
2
log
n
+ 9
.
84
dz
+3
.
92
z
2
ln2
n
−
11
−
p
′
with time complexity
O
(
n
2
log
n
)
. Compared with this work,we advance a classic randomized construction for
d
disjunctmatrix, namely, random incidence construction [1][2], to generate a
(
d,z
)
disjunct matrix which can not only generatecomparably smaller
t
×
n
matrix, but also handle the case where
z
is not known beforehand, instead, only the error probabilityof each test is bounded by some constant
γ
. Although
z
can bequite loosely upperbounded by
γt
, yet
t
is not an input. Themotivation of this construction lies in the real test scenarios,the error probability of each test is unknown and asymmetric,hence it is impossible to evaluate
z
before knowing the numberof pools.We only show the performance of this new construction,namely, ETG algorithm in this section. For the review purpose,we include the details of the construction and proofs in theAppendix.
Theorem 3.2:
ETG algorithm produces a
(
d,z
)
disjunct matrix with
t
= 2
(
d
+ 1)
d
+1
d
d
z
−
1 + ln(11
−
p
′
) + (
d
+ 1)ln
n
rows with probability
p
′
for an arbitrarily large constant
p
′
.
Corollary 3.1:
The
(
d,z
)
disjunct matrix is asymptoticallysmaller than the one constructed by Cheng [19].
Corollary 3.2:
The time complexity of
ETG
algorithm isasymptotically smaller than that of Cheng’s algorithm, giventhat
d <
√
n
.
Corollary 3.3:
Given that each test has an independent errorprobability
γ
, ETG algorithm produces a
(
d,z
)
disjunct matrixwith
t
=
τ
ln
n
(
d
+1)
2
−
2
τ
(
d
+1)ln(1
−
p
′
)(
τ
−
γ
(
d
+1))
2
with probability
p
′
,where
τ
= (
d/
(
d
+ 1))
d
.
4 T
RIGGER
I
DENTIFICATION
P
ROCEDURE FOR
B
ASIC
A
TTACKER
M
ODEL
In this section, we present the trigger identiﬁcationprocedure for the basic attacker model, where the jammers
deterministically
and
immediately
broadcasts jamming signalson the particular channel which carries the sensed messagetransmissions between sensor nodes. Therefore, as longas some jamming signals are received, at least one of thebroadcasting victim nodes is a trigger. In the next section,we will further investigate the performance of our solutiontowards some sophisticated attack models, in order to showthe robustness of this scheme in real scenarios.
4.1 Identiﬁcation Overview
The trigger identiﬁcation can be sketched as follows (Fig. 3):Assume that at the beginning of the identiﬁcation phase, all jammer nodes are idle and all the victim nodes in grey andblue have been discovered beforehand. The set of victims aredivided into interferencefree teams, where the transmissions of victim nodes within one team will not invoke a jammer node,whose interference signals will disrupt the communicationswithin another team, as shown in Fig. 3. We call these teams
testing teams
in the remainder of the paper.
Base StationSensor
Field
J
1
J
3
Sensor Nodes
J
2
V
1
V
2
V
4
V
5
V
7
V
6
V
10
V
13
V
11
V
12
V
19
V
8
V
20
V
18
V
15
V
14
V
17
V
9
r
R
J
2
R’
BS
Fig. 3. Nodes in grey and blue are victim nodes around jammer nodes, where blue nodes are also trigger nodes,which invoke the jammer nodes.
The identiﬁcation of trigger nodes involves two paralleltesting types: (1) Denote the set of victim nodes within each
testing team
as
W
, and the number of trigger nodes (tobe estimated) as
d
, then a group testing procedure will runsimultaneously over each
testing team
, to identify the
d
triggernodes from

W

victim ones; (2) Victim nodes within each
testing team
will be divided into the multiple
group
s, accordingto a randomized
(
d,
1)
disjunct matrix, as mentioned in Section3.2. Each group of victim nodes will be tested on a differentchannel, to avoid interference among groups.The testing procedure within each pool is twofold: (1) Eachgroup
i
is corresponding to a row in the testing matrix
M
, andassigned with a different channel frequency
f
from that of other groups. Let a victim node
j
broadcast a single bit on
f
,
iff
M
[
i,j
] = 1
, to activate possible jammer nodes nearby.Assume
M
has
t
rows and each sensor has
m
radios, thenonly
m
groups can be tested at a time, and all
t
groups canbe tested within
⌈
tm
⌉
rounds. This is because one victim node