Label based dv-hop localization against wormhole attacks in wireless sensor networks

Label-Based DV-Hop Localization Against Wormhole Attacks
in Wireless Sensor Networks

Junfeng Wu†,§ , Honglong Chen‡ , Wei Lou‡ , Zhibo Wang† , and Zhi Wang†
†
State Key Lab of Industrial Control Technology, Zhejiang University, China
‡
Dept. of Computing, The Hong Kong Polytechnic University, Hong Kong
§
Dept. of Electronic and Computer Engineering, The Hong Kong University of Science and Technology, Hong Kong
jfwu@ust.hk, {cshlchen, csweilou}@comp.polyu.edu.hk, {zbwang, wangzhi}@iipc.zju.edu.cn

Abstract sensed data make no sense without the nodes’ position
information. Hence, nodes are required to locate them-
Node localization becomes an important issue in the selves in many WSN applications, such as environment
wireless sensor network as its broad applications in en- monitoring, emergency rescue, and battlefield surveillance,
vironment monitoring, emergency rescue and battlefield to name a few.
surveillance, etc. Basically, the DV-Hop localization mech- Many protocols and algorithms are designed to solve
anism can work well with the assistance of beacon nodes the node’s positioning problem, which are categorized into
that have the capability of self-positioning. However, if two categories: range-based and range-free [2]. Range-
the network is invaded by a wormhole attack, the at- based protocols calculate the location using the point-to-
tacker can tunnel the packets via the wormhole link to point distance (or angle) estimates. Though range-based
cause severe impacts on the DV-Hop localization process. schemes are able to obtain relatively accurate results,
The distance-vector propagation phase during the DV- they can be applied only when nodes are equipped with
Hop localization even aggravates the positioning result, sophisticated hardware. Range-free solutions do not rely
compared to the localization schemes without wormhole on the availability of range (or angle) estimates, so they
attacks. In this paper, we analyze the impacts of wormhole need no expensive hardware. Considering that the hard-
attack on DV-Hop localization scheme. Based on the basic ware requirement of range-based solutions is inappropriate
DV-Hop localization process, we propose a label-based for resource-constrained WSNs, researchers are pursuing
secure localization scheme to defend against the wormhole range-free localization techniques as a cost-effective alter-
attack. Simulation results demonstrate that our proposed native [2].
secure localization scheme is capable of detecting the The DV-Hop [3] localization, as a range-free positioning
wormhole attack and resisting its adverse impacts with a algorithm, is applied with the assumption of isotropic
high probability. networks. First, beacons, as location-known nodes, flood
their positions through the network so that all nodes in the
Keywords: DV-Hop localization; wireless sensor net-
network can obtain the hop-counts to each of the beacons.
works; wormhole attack.
Then each beacon, after receiving the position information
from other beacons, calculates the average distance per
hop, which is also broadcasted among its neighborhood, by
I. Introduction averaging the distances to all other beacons over the hop-
counts. Sensors, being location unknown, estimate their
With the advantages of low cost, large scale, densely locations to corresponding beacons, based on the received
distributed deployment, self-configuration, etc., wireless beacons’ locations, average distance per hop and hop-
sensor networks (WSNs) have been applied in many fields counts.
to monitor and control the physical world [1]. In WSNs, As sensor networks usually work in a hostile environ-

978-0-7695-4134-1/10 $26.00 c 2010 IEEE.

ment, they are vulnerable to various malicious attacks. computation in the presence of attackers. In [7], a secure
The wormhole attack, as a typical external attack, can localization scheme is presented to make the location
be easily launched by two colluding attackers without the estimation of the sensor secure, by transmitting nonces
system’s authorization. When such attack is initiated, one at different power levels from beacon nodes. The secure
attacker tunnels its received packets to another attacker, localization approach in [8] relies on a set of covert base
thus, packets can be delivered through a shorter path. The stations, whose positions are unknown to the attacker
wormhole attack can deteriorate the DV-Hop localization during the localization. The covert base stations listen to
dramatically. It not only reduces the hop-counts to all the the beacon signals sent by the nodes and compute the
beacons in the network, but also contaminates the average nodes’ positions, then check the validity of the nodes.
distance per hop. As a result, the location estimate will be Lazos et al. [9] propose a robust positioning system
far away from precision. called ROPE that allows sensors to determine their loca-
In this paper, we focus on defending against the worm- tions without centralized computation. In addition, ROPE
hole attack in the DV-Hop localization process, i.e., over- provides a location verification mechanism that verifies
coming the impacts of the wormhole attack on the DV-Hop the location claims of the sensors before data collection.
localization. We propose a label-based secure localization In [10], a suit of techniques are introduced to detect
scheme which is wormhole attack resistant based on the malicious beacons that supply incorrect information to the
DV-Hop localization process. The main idea of our scheme sensor nodes. These techniques include a method to detect
is to generate a pseudo neighbor list for each beacon node, malicious beacon signals and techniques to detect replayed
use all pseudo neighbor lists received from neighboring beacon signals, identify malicious beacons, avoid false
beacon nodes to classify all attacked nodes into different detections and revoke malicious beacons. In [11], robust
groups, and then label all neighboring nodes (including statistical methods are proposed, including triangulation
beacons and sensors). According to the labels of neighbor- and RF-based fingerprinting, to make localization attack-
ing nodes, each node prohibits the communications with tolerant.
its pseudo neighbors, which are attacked by the wormhole For the wormhole attack detection, Hu at el. [12] present
attack. a general mechanism called packet leashes based on the
The main contributions of this paper include: (1) We notions of geographical and temporal leashes. Wang and
analyze the impact of the wormhole attack on the DV-Hop Bhargava [13] propose to detect the wormhole by visual-
localization process; (2) We propose a wormhole attack izing the anomalies introduced by the attack, which needs
resistant approach that can remove the packets delivered all the distance messages between each pair of nodes. To
through the wormhole link to achieve secure localization; make it suitable for large scale network, Wang and Lu [14]
(3) We conduct the simulation to validate the effectiveness propose an interactive wormhole detection which selects
of our proposed secure localization scheme. some feature points to reduce the overlapping issue and
The rest of this paper is organized as follows. Section II preserve major topology features. Xu at el. [15] propose a
reviews the related work on the secure localization. In wormhole attack detection algorithm using a hop counting
Section III, we describe the network model, the DV-Hop technique as a probe procedure, reconstructing a local map
localization approach, and the wormhole attack model and for each node and using a “diameter” feature to detect
its impacts on the DV-Hop localization process. Section IV abnormalities caused by wormholes. In [16], the wormhole
describes our proposed label-based secure localization in attack detection scheme adopts the maximum number of
details. In Section V, we present the performance evalua- independent neighbors of two non-neighbor nodes.
tion. Finally, Section V concludes this paper and outlines
As the localization process will be greatly deteriorated
our future work.
by the wormhole attack, some secure localization ap-
proaches have been proposed. SeRLoc [17] uses directional
II. Related Work antennas to detect the wormhole attack based on the sector
uniqueness property and communication range violation
The secure localization [4] has been well studied in property. The secure localization can be obtained after
the recent decade. We first review the range-based secure detecting the attacked locators. HiRLoc [18] further im-
localization systems and range-free secure localization proves SeRLoc by utilizing antenna rotations and multiple
systems respectively, and then discuss the schemes against transmission power levels to provide richer information
wormhole attack. for higher localization resolution. Chen et al. [19], [20]
Liu et al. [5] propose two secure localization schemes propose a secure localization scheme using the distance
against the compromise attack which adopt the concept of consistency to defend against the wormhole attack. In
consistency. SPINE [6] enables verifiable multilateration [21], inter-node messaging properties are used to detect
and verification of positions of mobile devices for secure the abnormality of the network when the wormhole attack

S3 S6 B2
exists. A so-called conflicting set is built to detect the S4 S5
B1
wormhole attack and to further resist against the impact
of the attack on the localization. However, all these ap-
A1
proaches [19], [20], [21] are proposed to deal with the Wor m hol e S2
range-based localization. In this paper, we address the Li nk
A2
security issue of the wormhole attack upon the range-free S1
DV-Hop-based localization process, which is so far never
been discussed in literature.
Senso r Beaco n Attacker

III. Problem Statement
Fig. 1. The impact of wormhole attack on DV-
Hop localization.
In this section, we describe the network model, the DV-
Hop localization approach, and the wormhole attack model
and its impacts on the DV-Hop localization process.
(xj , yj ) are the coordinates of beacons i and j respec-
tively, and hj is the hop-count value from beacon i to
A. Network Model
beacon j. Once calculated, HSi will also be flooded
to the sensors near to beacon i.
We assume that there are three types of nodes in a WSN:
• In the last phase, before conducting the self-
beacons, sensors, and attackers. Beacons are location-
localization, each sensor estimates the distance to
fixed nodes with their positions known in advance (by
each beacon based on its hop-count and the hop-
GPS device or manual configuration). The sensors, either
size to this beacon. Sensor k can get the distance
moving around or staying at a place, are position-unknown
dkj (distance from sensor k to beacon j) using
nodes that need to locate themselves with the assistance
dkj = hj × HSj . After obtaining all the distance
of beacons. The attackers exist in a pair and collude with
information, each sensor conducts the triangulation
each other to launch a wormhole attack, which can invade
or maximum likelihood estimation [22] to estimate its
the WSN without any system’s authorization. We assume
own location.
that all the nodes have an identical transmission range R
and each pair of nodes whose distance is within the range Note that the DV-Hop localization does not need any
R can communicate with each other with no packet loss. sophisticated hardware for the distance measurement, and
We also assume that sensors and beacons are de- thus, it is free from range measurement errors.
ployed independently, following the Poisson distribution
with node densities ρb and ρs , respectively. That is, the C. Wormhole Attack Model and Its Im-
probability of k beacons in an area Db and that of k sensors pacts on DV-Hop Localization
ρ k
in an area Ds are given as P (Nb = k) = (Dbk!b ) e−Db ρb
ρ k
and P (Ns = k) = (Dsk!s ) e−Ds ρs , respectively. In this paper, we consider an adversarial environment
where the localization procedure of sensors is attacked by a
B. DV-Hop Localization Approach wormhole attack. During the wormhole attack, when one
attacker receives packets at one point of the network, it
forwards the packets through the wormhole link to the
The DV-Hop localization approach has three phases [3]:
other attacker, which retransmits them at the other point
• In the first phase, a typical distance vector routing
of the network. We assume that the wormhole link is bi-
mechanism is employed. Beacons flood their location
directional and symmetrical so that the packets could be
information throughout the network with the initial
transmitted via either direction. Considering that if the
hop-count of 0. Each node that relays the message
length of the wormhole link is less than R, both attackers
increases the hop-count by one. After the flooding
are within each other’s transmission range such that the
procedure, every node can obtain the minimum hop-
packets transmitted by one attacker can be received and
count to each beacon.
retransmitted by the other attacker, resulting in endless
• In the second phase, each beacon, after obtain-
packet transmission loop. To exclude this exceptional case,
ing the position and hop-count information to all
we simply assume that the length of the wormhole link is
other beacons, estimates the average distance per
larger than R.
hop. Beacon i calculates the average distance per
The wormhole attack can greatly deteriorate the DV-
hop, called√ as hop-size HS, using the formula
(xi −xj )2 +(yi −yj )2
Hop localization procedure. As shown in Fig. 1, two at-
HSi = j=i hj , where (xi , yi ) and tackers A1 and A2 collude to launch a wormhole attack in

Beac on Nodes Sensor Nodes DV-Hop Based
Labeling Labeling Sec ure Loc alization S2 S1
W o rmho le B6
Link S5
B2
Fig. 2. The flowchart of the label-based DV- B3
A2 A1
Hop localization scheme. B5

S4
S3
S6
the network. In the first phase of the DV-Hop localization, B1
B4
beacons B1 and B2 initiate the flooding in the network
so that other nodes can obtain the hop-counts to these
beacons. For instance, the original minimum hop-count
to beacon B2 for sensor S1 is 6 (B2 → S6 → S5 →
S4 → S3 → B1 → S1 ). However, the flooding message
from beacon B2 would be received by S2 , then relayed by Senso r Beaco n Attacker
the wormhole link to S1 . Consequently, S1 will consider
the minimum hop-count to B2 as 2, which is less than
Fig. 3. The wormhole attack in a WSN.
the real value 6. The wormhole attack can also affect
the second phase of the DV-Hop localization when the
beacons calculate the hop-size. As shown in Fig. 1, the some of which are borrowed from our previous work [21]:
original minimum hop-count √ from B1 to B2 is 5, B1 Definition 1. Duplex Wormhole Attack : A node is under
(x1 −x2 )2 +(y1 −y2 )2
will calculate the hop-size as , where a duplex wormhole attack if it lies in the common trans-
5
(x1 , y1 ) and(x2 , y2 ) are the coordinates of beacons B1 and mission area of the two attackers.
B2 . However, as the existence of the wormhole attack, B1 Definition 2. Simplex Wormhole Attack: A node is under a
will get a minimum hop-count to B2 as 3, the hop-size
√ simplex wormhole attack if it lies only in the transmission
(x1 −x2 )2 +(y1 −y2 )2 range of either one attacker but not in the common
calculated by B1 will be 3 , which is
transmission area of the two attackers.
larger than the real value. Therefore, the wormhole attack
Definition 3. Pseudo Neighbor: A node is a pseudo
can disturb the first two phases of the DV-Hop localization.
neighbor if it can be communicated with via the wormhole
In the first phase, a sensor may obtain a smaller hop-counts
link.
to beacons. In the second phase, a beacon may calculate
For the network shown in Fig. 3, node S4 is under the
an incorrect hop-size, which is delivered to its neighboring
duplex wormhole attack, node S3 is under the simplex
sensors. Finally, each sensor may use incorrect hop-counts
wormhole attack. Node B6 is a pseudo neighbor of node
and hop-size to estimate the distances to all the beacons
B1 .
for the self-localization.
To ease the description of our proposed scheme, we
also define DR (u) as a disk with radius R and center
IV. Label-Based DV-Hop Localization u; LN (i) and LP (i) are defined as the neighbor list and
pseudo neighbor list of node i, respectively.
In this section, we describe our proposed wormhole
attack resistant localization scheme, called label-based DV- A. Beacon Nodes Labeling
Hop localization. The label-based DV-Hop localization
scheme includes three phases, beacon nodes labeling, sen- Since nodes in the network, including both beacons
sor nodes labeling, and DV-Hop-based secure localization. and sensors, periodically broadcast Hello messages to
The flowchart of the label-based DV-Hop localization its neighbors, each node can build a neighbor list after
scheme is shown in Fig. 2. Firstly, the beacon nodes are receiving the Hello messages from its neighbors. The Hello
differentiated and labeled according to their geographic message include the node’s type (i.e., beacon or sensor),
relationship under a wormhole attack. The sensor nodes identification, and coordinate if its type is “beacon”. When
are further differentiated and labeled by using the labeling building the neighbor lists, the beacon nodes may observe
results of neighboring beacon nodes. After eliminating the some abnormalities due to the existence of a wormhole
illegal connections among the labeled neighboring nodes attack. By examining these abnormalities, the beacon
which are contaminated by the wormhole attack, the DV- nodes can be classified and labeled into three categories:
Hop localization procedure can be successfully conducted. beacon nodes under the duplex wormhole attack, beacon
To describe the label-based DV-Hop localization nodes under the simplex wormhole attack, and beacon
scheme more clearly, we provide the following definitions, nodes without the wormhole attack. As shown in Fig. 3,

beacon nodes in the region DR (A1 ) ∩ DR (A2 ) are under B1 can observe that it receives a message from a node
the duplex wormhole attack, beacon nodes in the regions which is outside its transmission range. Thus, it can
DR (A1 )DR (A2 ) and DR (A2 )DR (A1 ) are under the determine that it is under a wormhole attack.
simplex wormhole attack, and beacon nodes outside the Beacon Labeling Scheme BL3: Every beacon node
region DR (A1 )∪DR (A2 ) are without the wormhole attack. checks whether it violates the transmission constraint
The classification of the beacon nodes is according to the property when building its neighbor list. If the trans-
following three properties: mission constraint property is broken, it determines
that it is under a wormhole attack.
• Self-exclusion property: A node normally cannot
hear a message sent from itself in a loop-free path. The basic beacon labeling algorithm uses the above
For each beacon node under the duplex wormhole at- three schemes to classify the beacons, which is shown in
tack (i.e., the beacon node lies in the region DR (A1 )∩ Algorithm 1: Every node periodically broadcasts a Hello
DR (A2 ) as shown in Fig. 3), the Hello message message. It also receives the Hello messages from its
it sends will be relayed by attacker A1 through neighboring nodes to build its neighbor list. Each beacon
wormhole link to attacker A2 and then received by node initially labels itself with ‘N’. It further classifies
itself; similarly, the message will also be transmitted itself using the beacon labeling schemes BL1, BL2 and
from A2 to A1 via wormhole link and then received BL3. If the beacon node detects that it violates the self-
by itself. Therefore, the beacons under the duplex exclusion property using the scheme BL1, it labels itself
wormhole attack can be identified using the self- with ‘D’ to indicate that it is under the duplex wormhole
exclusion property. attack. Otherwise, if the beacon node detects that it is under
Beacon Labeling Scheme BL1: Every beacon node the simplex wormhole attack using the schemes BL2 or
checks whether it violates the self-exclusion property BL3, it labels itself with ‘S’ to indicate that it is under the
when building its neighbor list. The beacon node simplex wormhole attack. Note that for those beacon nodes
which violates the self-exclusion property can deter- that do not violate any property, their labels will be kept
mine that it is under the duplex wormhole attack. with ‘N’s to indicate that they are without the wormhole
• Packet uniqueness property: A node normally can- attack.
not receive more than one copy of the same packet
from any one of its neighbors. Algorithm 1 Basic Beacon Node Labeling
As shown in Fig. 3, beacon node B4 lies in the 1: Each node Bi periodically broadcasts a Hello message
common transmission region of attacker A1 and bea- to its neighbors and receives Hello messages to build
con B1 , i.e., DR (A1 ) ∩ DR (B1 ). B1 can receive its neighbor list.
Hello message from B4 twice: one directly from 2: Each beacon node is initially labeled with ‘N’.
B2 and the other from A2 (A1 relays the message 3: if Bi detects the duplex wormhole attack using scheme
via the wormhole link to A2 after receiving it from BL1 then
B4 ). Therefore, if a beacon node receives the same 4: Bi is labeled with ‘D’.
message more than once from a neighbor node, it is 5: end if
under a wormhole attack. 6: if Bi detects the simplex wormhole attack using
Beacon Labeling Scheme BL2: Every beacon node schemes BL2 and BL3 then
checks whether it violates the packet uniqueness 7: Bi is labeled with ‘S’.
property. If it does, i.e., it receives more than one 8: end if
copy of the same packet from one of its neighbors,
it can determine that it is under a wormhole attack
(either a duplex or simplex wormhole attack). After all beacon nodes are classified, we have the
• Transmission constraint property: A node normally following theorems:
cannot communicate with nodes outside its transmis- Theorem 1. Given a network under the wormhole attack,
sion range. any beacon node under the simplex wormhole attack can
As shown in Fig. 3, beacon node B5 lies outside detect all its pseudo neighboring beacons.
the transmission region of beacon node B1 . However, Proof: For any beacon node under the simplex worm-
the Hello message transmitted by B5 can be received hole attack, it lies in (DR (A1 ) DR (A2 )) ∪ (DR (A2 )
by attacker A1 , after that A1 will relay it through DR (A1 )). Without loss of generality, we take beacon node
the wormhole link to A2 which will further relay it B1 , which lies in DR (A2 ) DR (A1 ) as shown in Fig. 3,
to B1 . When receiving the Hello message from B5 , for discussion. All the pseudo neighboring beacons of B1
B1 can calculate the distance between them as the are located in DR (A1 ), which can be grouped into two
coordinate of B5 is included in this Hello message. groups:

Group 1: The pseudo neighboring beacons of B1 lie in tical pseudo neighboring beacon list, i.e., LP (B1 ) =
DR (A1 ) ∩ DR (B1 ) (e.g., B3 and B4 in Fig. 3). As the LP (B2 ) ={B3 , B4 , B5 , B6 }.
Hello messages of these pseudo neighboring beacons can We further classify the beacons labeled ‘S’ into two
arrive at B1 twice, one directly received by B1 , the other categories according to their geographic locations, i.e., the
one relayed by the wormhole attack and then received by beacons lie in the transmission range of the same attacker
B1 , B1 can identify all these pseudo neighboring beacons are grouped into one category. After beacons build their
using the beacon labeling scheme BL2. pseudo neighboring beacon lists, two neighboring beacons
Group 2: The pseudo neighboring beacons of B1 lie exchange their pseudo neighboring beacon lists with each
in DR (A1 ) DR (B1 ) (e.g., B5 and B6 in Fig. 3). For other so that they can compare the pseudo neighboring
these beacons, the Hello messages they send can be relayed beacon list received from its neighboring beacon with
by the wormhole attack and received by B1 . Therefore, its own pseudo neighboring beacon list. If two pseudo
B1 can also identify all these pseudo neighboring beacons neighboring beacon lists are identical, these two beacons
using the beacon labeling scheme BL3. belong to the same category; otherwise, they belong to
Therefore, any beacon node under the simplex worm- different categories. These two categories of beacons are
hole attack can detect all its pseudo neighboring beacons. called as attacked beacon set one (ADS-1) and attacked
beacon set two (ADS-2). When comparing the nodes in
Theorem 2. Given a network under the wormhole attack, these two sets, the set which has the beacon with the
two beacon nodes under the simplex wormhole attack lie minimum ID among those different beacons is named as
in the transmission range of the same attacker if and only ADS-1 and all beacons in this set are labeled with ‘S1’;
if their pseudo neighboring beacon lists are identical. the other set is named as ADS-2 and all beacons in the
Proof: Necessary condition: For any two beacon nodes set are labeled with ‘S2’. Take B1 , B2 and B5 in Fig. 3
under the simplex wormhole attack that are attacked by for example, LP (B1 ) = LP (B2 ) = {B3 , B4 , B5 , B6 },
the same attacker, without loss of generality, we take the LP (B5 ) = {B1 , B2 , B3 }. After exchanging the pseudo
beacons that lie in DR (A2 ) (e.g., B1 and B2 as shown neighboring beacon lists with each other, B1 can observe
in Fig. 3) for discussion. From Theorem 1, we can see that LP (B1 ) = LP (B2 ) and LP (B1 ) = LP (B5 ), thus, B1
that each of such beacon nodes can identify all its pseudo determines that B1 and B2 belong to the same category
neighboring beacons, which lie in DR (A1 ). Therefore, and B5 belongs to the other category. Moreover, B1 and
their pseudo neighboring beacon lists, which include all B2 are labeled with ‘S1’ and B4 , B5 and B6 are labeled
beacons within DR (A1 ), are identical. with ‘S2’ as B1 has the minimum node ID among them.
Sufﬁcient condition: For any two beacon nodes under Note that B3 is labeled with ‘D’ since it is under the duplex
the simplex wormhole attack, the possible scenarios are wormhole attack.
(1) both beacon nodes lie in DR (A1 ), (2) both beacon The advanced beacon node labeling algorithm is shown
nodes lie in DR (A2 ), and (3) one beacon node lies in in Algorithm 2. Every beacon node Bi which is under
DR (A1 ) and the other one lies in DR (A2 ). We now proof the simplex wormhole attack (labeled ‘S’) broadcasts
by contradiction that if these two beacon nodes have the a PseudoNeighborBeacon message including its pseudo
identical pseudo neighboring beacon list, scenario 3 is neighboring beacon list. It also collects the PseudoNeigh-
impossible. Assume scenario 3 is possible. Without loss of borBeacon messages from its neighboring beacons. Bi
generality, we assume, for two beacon nodes B1 and B2 then builds the ADS-1 and ADS-2 based on these pseudo
under the simplex wormhole attack, B1 lies in DR (A1 ) and neighboring beacon lists. Bi searches itself in these two
B2 lies in DR (A2 ). From Theorem 1, B1 will detect B2 sets, if it is found in ADS-1, Bi is labeled with ‘S1’;
to be a pseudo neighboring beacon. As B1 and B2 have otherwise, Bi is labeled with‘S2’.
the identical pseudo neighboring beacon list, B2 is also
in B2 ’s pseudo neighboring beacon list, which suggests B. Sensor Nodes Labeling
that B2 lies in DR (A1 ). As B2 lies in both DR (A1 )
and DR (A2 ), i.e., B2 lies in DR (A1 ) ∩ DR (B1 ), B2 is In the previous subsection, we have just labeled the
under the duplex wormhole attack, which contradicts to beacon nodes in the network with ‘D’, ‘S1’, ‘S2’, or
the assumption that B2 is under the simplex wormhole ‘N’. This is not adequate for the localization procedure
attack. Therefore, scenario 3 is impossible. For scenarios to defend against the wormhole attack. Therefore, in this
1 and 2, both beacon nodes lie in the transmission range subsection, we will further label the sensor nodes in the
of the same attacker. network. Similar to the beacon nodes, if sensor nodes lie
We can see this from the example shown in Fig. 3. in region DR (A1 ) ∪ DR (A2 ) (as shown in Fig. 3), they
B1 and B2 are under a simplex wormhole attack, and are attacked by the wormhole attack; if sensors lie outside
they both locate in DR (A2 ), thus, they have the iden- the above region, they are not attacked by the wormhole

Algorithm 2 Advanced Beacon Node Labeling node can conclude that it is under the simplex wormhole
1: Each beacon node Bi labeled with ‘S’ broadcasts a attack and labels itself with ‘S’.
PseudoNeighborBeacon message including its pseudo For the sensor nodes labeled with ‘S’, they can further
neighboring beacon list and receives the pseudo neigh- use the following extended sensor labeling schemes:
boring beacon lists from its neighboring beacons’
Extended Sensor Labeling Scheme ESL1: For a sensor
PseudoNeighborBeacon messages.
Si labeled with ‘S’, it will check the beacons in both
2: Bi builds the ADS-1 and ADS-2 based on these
attacked beacon sets after it receives the Alert message.
pseudo neighboring beacon lists.
If it can find a beacon Bj that is not in the neighbor list
3: Bi searches itself in both sets.
of Si , Si will will mark itself with the label of Bj .
4: if Bi is found in the ADS-1 then
5: Bi is labeled with ‘S1’. Extended Sensor Labeling Scheme ESL2: For a sensor
6: else labeled with ‘S’ using scheme SL2, if the received two
7: Bi is labeled with ‘S2’. copies of the same message are from one beacon node,
8: end if the sensor further checks the label of this beacon node.
If the beacon node is labeled with ‘S1’, the sensor labels
itself with ‘S2’; otherwise, if the beacon node is labeled
attack. with ‘S2’, the sensor labels itself with ‘S1’.
Each attacked beacon node broadcasts an Alert message Extended Sensor Labeling Scheme ESL3: For a sensor
if it is being labeled with ‘S1’, ‘S2’ or ‘D’. The Alert labeled with ‘S’ using scheme SL3, if one of these two
message includes its label, the attacked beacon set and its received beacon nodes is labeled with ‘N’, the sensor
members’ labels. For each beacon node with a label ‘D’, further checks the label of the other beacon node. If the
its attacked beacon set will include all beacons in region other is labeled with ‘S1’, the sensor labels itself with
DR (A1 ) ∪ DR (A2 ). ‘S2’; otherwise, if the other is labeled with ‘S2’, the sensor
Initially, each sensor node will label itself with ‘N’. labels itself with ‘S1’.
After receiving an Alert message from any of its neigh- The next sensor labeling scheme can be used to label
boring beacons, the sensor node relabels itself with ‘U’ an uncertain sensor if it is not under the wormhole attack.
to indicate that the sensor node may be affected by the Sensor Labeling Scheme SL4: For a sensor Si labeled
wormhole attack and its final label is still uncertain. For with ‘U’, it will check the beacons in both attacked beacon
each sensor node labeled with ‘U’, it will further conduct sets after it receives the Alert message. If Si can find one
the following labeling schemes1 . beacon in each set, i.e., one beacon in the ADS-1 and one
Similar to the beacon labeling scheme BL1, sensor beacon in the ADS-2, such that these two beacons are not
labeling scheme SL1 is used to detect if a sensor node in the neighbor list of Si , then Si can conclude that it is
is under the duplex wormhole attack. not under the wormhole attack and will mark itself with
Sensor Labeling Scheme SL1: Each sensor node labeled label ‘N’.
with ‘U’ checks whether it violates the self-exclusion The sensor nodes labeling scheme is illustrated in
property. If yes, it determines that it is under the duplex Algorithm 3. Each sensor node is initially labeled with ‘N’.
wormhole attack. The sensor node will mark itself with If it receives an Alert message from a neighboring beacon,
label ‘D’. it labels itself with ‘U’. The sensors labeled with ‘U’ can
Sensor nodes can use the following schemes to label build the two attacked beacon sets after receiving all Alert
themselves if they are under the simplex wormhole attack. messages from their neighboring beacon nodes. After that,
Sensor Labeling Scheme SL2: For a sensor labeled with the sensor nodes labeled with ‘U’ conduct the sensor nodes
‘U’ but not ‘D’, if it receives two copies of the same labeling schemes SL1, SL2, SL3 and SL4. The sensor
message from its neighbor node, it can conclude that it is nodes labeled with ‘S’ further conduct the extended sensor
under the simplex wormhole attack and labels itself with nodes labeling schemes ESL1, ESL2 and ESL3.
‘S’.
C. DV-Hop Based Secure Localization
Sensor Labeling Scheme SL3: For a sensor labeled with
‘U’ but not ‘D’, if it receives messages from two beacon
As the existence of the wormhole attack, a node may
nodes, it can calculate the distance between these two
receive messages from its pseudo neighbors. The DV-Hop
beacon nodes as their coordinates can be obtained from
localization is therefore deteriorated. To obtain a successful
the messages. If the distance is larger than 2R, the sensor
positioning for the DV-Hop-based localization, each node
1 The proof of correctness of these labeling schemes is omitted due to has to eliminate those pseudo neighbors from its neighbor
space limitations. list. Considering that nodes may be labeled with ‘N’, ‘U’,

Algorithm 3 Sensor Nodes Labeling avoided. Thus, our proposed scheme can obtain the secure
1: Initially, each sensor node is labeled with ‘N’. localization against the wormhole attack.
2: Each sensor labels itself with ‘U’ if it receives an Alert
message from a neighboring beacon. V. Performance Evaluation
3: if Sensor Si is labeled with ‘U’ then
4: Si builds the two attacked beacon sets based on the
In this section, we firstly build the theoretical model
received Alert messages.
for determining the probability of detecting the wormhole
5: Si conducts the sensor nodes labeling schemes SL1,
attack successfully. After that, the simulation results are
SL2, SL3 and SL4.
presented to validate our theoretical model and evaluate
6: if Si is labeled with ‘S’ then
our proposed secure localization scheme.
7: Si conducts the extended sensor nodes labeling
schemes ESL1, ESL2 and ESL3.
A. Theoretical Probability of Wormhole
8: end if
Attack Detection
9: end if

According to the beacon nodes labeling schemes, as
long as there are beacon nodes in the communication range
‘D’, ‘S’, ‘S1’, ‘S2’, different labeled nodes will execute the of the two attackers, these beacon nodes can detect the
elimination operations according to the following rules2 : wormhole attack successfully. Let Ps denote the theoret-
• For each node (beacon or sensor) with label ‘N’: no ical probability that beacon nodes successfully detect the
removing operation is needed. wormhole attack, while Pf denotes the probability that the
• For each node (beacon or sensor) with label ‘D’: 1) beacon nodes fail to detect the wormhole attack. Hence
remove sensors with label ‘U’; 2) remove beacons and we have: Ps = 1 − Pf . As shown in Fig. 3, the wormhole
sensors with labels ‘S1’, ‘S2’ or ‘S’ if only one copy attack cannot be detected only under the following two
of the message can be received from these beacons scenarios: 1) there is no beacon node in DR (A1 ); and 2)
and sensors; 3) remove beacons and sensors with label there is no beacon node in DR (A2 ).
‘D’ if exactly two copies of the same message can be As the beacon nodes are randomly deployed in the
received from these beacons and sensors. network with density ρb , the probability that there is no
• For each node (beacon or sensor) with label ‘S1’: 1) beacon node in DR (A1 ) is P (A) = e−ρb DR (A1 ) . Similarly,
remove beacons and sensors with labels ‘U’, ‘D’ or the probability that there is no beacon node in DR (A2 ) is
‘S’; 2) remove beacons and sensors with label ‘S2’ if P (B) = e−ρb DR (A2 ) . Thus, we can get:
only one copy of the message can be received from
these beacons and sensors. Pf = P (A ∪ B) = P (A) + P (B) − P (AB)
• For each node (beacon or sensor) with label ‘S2’: 1) 2
= 2e−ρb πR − e−ρb DR (A1 )∩DR (A2 ) (1)
remove beacons and sensors with labels ‘U’, ‘D’ or
‘S’; 2) remove beacons and sensors with label ‘S1’ if
only one copy of the message can be received from Therefore, the probability of the wormhole attack de-
these beacons and sensors. tection is:
• For each sensor with label ‘U’: remove beacons and
sensors with labels ‘U’, ‘D’, ‘S1’, ‘S2’ or ‘S’. Ps = 1 − Pf
• For each sensor with label ‘S’: 1) remove beacons 2
and sensors with labels ‘U’, ‘S1’ or ‘S2’; 2) remove = 1 − 2e−ρb πR + e−ρb DR (A1 )∩DR (A2 ) (2)
beacons and sensors with labels ‘S’ or ‘D’ if only
one copy of the message can be received from these
beacons and sensors. B. Simulation Evaluation
After each node eliminates the abnormal nodes from its
neighbor list, the DV-Hop localization procedure will be The network configuration of our simulation is set as
conducted. In the first phase of the DV-Hop localization, follows: 100 nodes, including both the beacon nodes and
every node will not forward the message received from sensor nodes, are deployed randomly in a 50 × 50m2
the node out of its neighbor list. With this strategy, the region. The transmission range of each node equals to
impacts of the wormhole attack on the localization will be 10m. We evaluate the performance of our proposed scheme
when varying the ratio of beacons to sensors as well as
2 The proof of correctness of these rules is omitted due to space the ratio of the length of the wormhole link to the node
limitations. transmission range (L/R).

0.96 2

Basic DV−Hop Localization Without Wormhole Attack
1.8
Label−based DV−Hop Localization With Wormhole Attack
Probability of Wormhole Attack Detection

0.958 Basic DV−Hop Localization With Wormhole Attack
1.6

Relative Localization Error
1.4
0.956
1.2

1
0.954

0.8

0.952 0.6

0.4

0.95
1 1.5 2 2.5 3 0.2
0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5
L/R
Beacon Nodes Ratio

Fig. 4. Probability of wormhole attack detec- Fig. 6. Comparison of relative localization
tion. error.
1

0.95
Probability of Wormhole Attack Detection

0.9
Theoretical
Simulation
0.85

0.8

0.75
when the ratio of beacons to sensors is 50%.
0.7

0.65 The impacts of the wormhole attack on the DV-Hop
0.6 localization process and our proposed wormhole-attack-
0.55 resistent localization scheme are illustrated in Fig. 6 when
0.5 the ratio of beacons to sensors varies. In this ﬁgure, the
0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5
Beacon Nodes Ratio relative localization error is used to indicate the impact
of the wormhole attack on the localization scheme. The
Fig. 5. Probability of wormhole attack detec- curve with the label “Basic DV-Hop Localization Without
tion: Theoretical Model vs Simulation. Wormhole Attack” indicates the relative localization error
for the DV-Hop localization scheme when there is no
wormhole attack. We can see that the curve is quite
Fig. 4 illustrates the probability of the wormhole attack stable when the ratio of beacons to sensors varies, which
detection when varying the ratio of the length of the suggests that the accuracy of the DV-hop localization
wormhole link to the transmission range L/R. In this is insensitive to the number of beacons in the network.
ﬁgure, the ratio of beacon nodes to sensor nodes is set to Therefore, this curve is used as the reference when the
30%. We can see that the probability descends slightly with wormhole attack exists. The curve with the label “Basic
the increase of L/R. However, the probability keeps above DV-Hop Localization With Wormhole Attack” indicates
95.4%, implying that our proposed scheme can detect the the relative localization error for the DV-Hop localization
wormhole attack with a high probability. under the wormhole attack. We can see that when the
Fig. 5 shows the results of determining the probability wormhole exists, the relative localization error for the
of the wormhole attack detection through the theoretical DV-Hop localization scheme increases drastically, which
model and simulations. To analyze how the ratio of bea- demonstrates the negative impacts of the wormhole attack
cons to sensors effects the probability of the wormhole on the DV-Hop localization. However, for the label-based
attack detection, we set the L/R to 2 and vary the ratio DV-Hop localization under the wormhole attack, which is
of beacons to sensors from 10% to 50%. The curves in the curve with the label“Label-based DV-Hop Localization
Fig. 5 illuminate that the theoretical calculation of the With Wormhole Attack”, the relative localization error is
probability matches the simulation result quite well (with gradually close to that of the basic DV-Hop localization
the maximum difference of 3%). Also, when increasing without wormhole attack as the ratio of beacons to sensors
the ratio of beacons to sensors from 10% to 30%, the increases from 10% to 30%. When the ratio of beacons
probability of the wormhole attack detection raises up to sensors is larger than 30%, the label-based DV-Hop
drastically to almost 95%. After that the increasing trend can totally conquer the negative impacts of the wormhole
becomes slower. Finally, the probability reaches 99.6% attack on the localization process.

VI. Conclusion and Future Work [13] W. Wang and B. Bhargava, “Visualization of Wormholes in Sensor
Networks,” in Proc. of ACM WiSec, 2004.
[14] W. Wang and A. Lu, “Interactive wormhole detection and evalua-
In this paper, we analyze the severe impacts of the tion,” Information Visualization, vol. 6, no. 1, pp. 3–17, 2007.
wormhole attack on the DV-Hop based localization in wire- [15] Y. Xu, G. Chen, J. Ford, and F. Makedon, “Detecting Wormhole
less sensor networks. To tackle this secure problem, we Attacks in Wireless Sensor Networks,” in Proc. of IFIP, 2008.
[16] R. Maheshwari, J. Gao, and S. R. Das, “Detecting Wormhole
propose a label-based secure localization scheme to detect Attacks in Wireless Networks Using Connectivity Information,” in
and resist the wormhole attack for the DV-Hop localiza- Proc. of IEEE Infocom, 2007.
tion process. We also conduct simulations to demonstrate [17] L. Lazos and R. Poovendran, “SeRLoc: Robust Localization for
Wireless Sensor Networks,” ACM Trans. on Sensor Networks, pp.
the effectiveness of our proposed scheme under different 73–100, 2005.
network parameters. [18] ——, “HiRLoc: High-Resolution Robust Localization for Wireless
The proposed scheme works well in the scenario when Sensor Networks,” IEEE Journal on Selected Areas in Communi-
cations, vol. 24, no. 2, pp. 233–246, 2006.
the network has no packet loss, and the transmission ranges [19] H. Chen, W. Lou, and Z. Wang, “A Consistency-based Secure
of all nodes are identical. In our future work, we will Localization Scheme Against Wormhole Attacks in WSNs,” in Proc.
extend our secure localization scheme to tolerate the packet of the International Conference on Wireless Algorithms, Systems
and Applications (WASA), 2009.
loss. Also, we will consider the scenario when different [20] H. Chen, W. Lou, X. Sun, and Z. Wang, “A Secure Localization
types of nodes have different transmission ranges. Approach Against Wormhole Attacks Using Distance Consistency,”
Eurasip Journal on Wireless Communications and Networking,
Spacial Issue on Wireless Network Algorithms, Systems, and Ap-
VII. Acknowledgment plications, 2009.
[21] H. Chen, W. Lou, and Z. Wang, “Conﬂicting-Set-Based Worm-
hole Attack Resistant Localization in Wireless Sensor Networks,”
This work is supported in part by grants NSFC in Proc. 6th Int. Conf. on Ubiquitous Intelligence and Comput-
60873223, NSFC 90818010, International Cooperative ing(UIC), 2009.
Project of Science and Technology Department of Zhe- [22] K. Langendoen and N. Reijers, “Distributed Localization in Wire-
less Sensor Networks: a Quantitative Comparison,” Computer Net-
jiang Province (2009C34002), PolyU 5236/06E, PolyU works, pp. 449–518, 2003.
5243/08E, PolyU 5253/09E, 1-ZV5N, and ZJU-SKL
ICT0903.

References
[1] N. Bulusu, J. Heidemann, and D. Estrin, “GPS-less low cost outdoor
localization for very small devices,” pp. 28–34, 7 2000.
[2] T. He, C. Huang, B. Blum, J. A. Stankovic, and T. Abdelzaher,
“Range-Free Localization Schemes for Large Scale Sensor Net-
works,” in Proc. of ACM MOBICOM, 2003, pp. 81–95.
[3] D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS) using
AOA,” in Proc. of IEEE INFOCOM, 2003.
[4] A. Boukerche, H. A. B. F. Oliveira, E. F. Nakamura, and A. A. F.
Loureiro, “Secure Localization Algorithms for Wireless Sensor
Networks,” IEEE Communications Magazine, pp. 96–101, 2008.
[5] D. Liu, P. Ning, and W. Du, “Attack-Resistant Location Estimation
in Sensor Networks,” in Proc. of IEEE IPSN, 2005.
[6] S. Capkun and J. P. Hubaux, “Secure Positioning of Wireless
Devices with Application to Sensor Networks,” in Proc. of IEEE
INFOCOM, 2005.
[7] F. Anjum, S. Pandey, and P. Agrawal, “Secure Localization in
Sensor Networks using Transmission Range Variation,” in Proc.
of IEEE MASS, 2005.
[8] S. Capkun, M. Cagalj, and M. Srivastava, “Secure Localization With
Hidden and Mobile Base Stations,” in Proc. of IEEE INFOCOM,
2006.
[9] L. Lazos, R. Poovendran, and S. Capkun, “ROPE: Robust Position
Estimation in Wireless Sensor Networks,” in Proc. of IEEE IPSN,
2005.
[10] D. Liu, P. Ning, and W. Du, “Detecting Malicious Beacon Nodes
for Secure Localization Discovery in Wireless Sensor Networks,”
in Proc. of IEEE ICDCS, 2005.
[11] Z. Li, W. Trappe, Y. Zhang, and B. Nath, “Robust Statistical
Methods for Securing Wireless Localization in Sensor Networks,”
in Proc. of IEEE IPSN, 2005.
[12] Y. C. Hu, A. Perrig, and D. B. Johnson, “Packet Leashes: A Defense
Against Wormhole Attacks in Wireless Networks,” in Proc. of IEEE
INFOCOM, 2003.

Label based dv-hop localization against wormhole attacks in wireless sensor networks

Recommended

More Related Content

What's hot (18)

Similar to Label based dv-hop localization against wormhole attacks in wireless sensor networks (20)

More from ambitlick (20)

Recently uploaded (20)

Label based dv-hop localization against wormhole attacks in wireless sensor networks