Mobile Beacon Based Wormhole Attackers Detection and Positioning in Wireless Sensor Networks

Abstract

Wormhole attack is a severe attack that can be easily launched by a pair of external attackers in hostile wireless sensor networks. In the wormhole attack, an attacker sniffs packets at one point in the network, and tunnels them through the wormhole link to the other attacker at another point of the network, which broadcasts them to its neighbors. Such kind of procedure can easily deteriorate the normal functionality of the networks. In this paper, we propose a novel wormhole attackers detection and positioning scheme based on mobile beacon, which can not only detect the existence of wormhole attacks, but also accurately localize the attackers for the system to eliminate them out of the network. The main idea is to detect whether the communication between the mobile beacon and each of the static beacons violates the communication properties and then the attacker can be estimated as the center of its communication area by determining the intersection point of the chords’ perpendicular bisector. The simulation results illustrate that our proposed scheme can obtain a high wormhole attack detection probability as well as a high attackers positioning accuracy.

1. Introduction

Wireless Sensor Networks (WSNs) have been applied in more and more applications, such as the emergency response systems, military field operations, and environment monitoring systems, due to the development of the low-cost, low-power, and multifunctional sensor nodes. In normal WSN applications, the sensor nodes are organized to accomplish some kind of tasks, such as event detection or data gathering. However, since WSNs are usually deployed in hostile environments, which may be attacked by some malicious attacks, the functionality of networks may be interrupted. Therefore, security is a necessary characteristic of WSNs applications.

Attackers in WSNs can be classified into two categories, external attackers and internal attackers [1]. External attackers, such as the wormhole attack, can disrupt the network functionality without passing the system's authorization, while internal attackers, such as the compromise attack, are authenticated ones which can act as inner-network nodes to break the system's security.

Generally, the wormhole attack is launched by two colluding external attackers, which can disrupt or even collapse the functionality of the WSNs. In the wormhole attack, an attacker sniffs packets at one point in the network and tunnels them through the wormhole link to another attacker at the other point of the network, which broadcasts the packets to its neighboring nodes. Such a simple operation can severely affect the localization and routing procedures. For example, as shown in Figure 1, two kinds of nodes, that is, beacons and sensors, are deployed in the network, which is attacked by a wormhole attack lunched by $A_{\mathrm{1}}$ and $A_{\mathrm{2}}$ . Due to the existence of the wormhole attack, two nonneighboring nodes $S_{\mathrm{1}}$ and $S_{\mathrm{7}}$ will consider each other as its neighbor. Moreover, $S_{\mathrm{6}}$ will get a hop count 3 to $B_{\mathrm{1}}$ via the path $S_{\mathrm{6}}\to S_{\mathrm{7}}\stackrel{\to A_{\mathrm{2}}\to A_{\mathrm{1}}\to }{\to }{S}_{\mathrm{1}}\to B_{\mathrm{1}}$ since the relay behaviors of $A_{\mathrm{1}}$ and $A_{\mathrm{2}}$ are invisible to $S_{\mathrm{1}}$ , while the actual hop count should be 5 ( $S_{\mathrm{6}}\to S_{\mathrm{5}}\to S_{\mathrm{4}}\to S_{\mathrm{3}}\to S_{\mathrm{2}}\to B_{\mathrm{1}}$ ). Thus, the wormhole attack in Figure 1 can severely affect the self-localization of $S_{\mathrm{6}}$ when the DV-Hop localization scheme [2] is adopted.

Figure 1

The impacts of the wormhole attack on a WSN.

The above severe effects of the wormhole attack on WSN applications motivate us to propose an efficient scheme to defend against the wormhole attacks. In this paper, we first propose a novel wormhole attackers detection scheme which can detect the existence of the wormhole attacks with a high probability. Then we propose a basic positioning scheme to further localize the wormhole attackers. We also propose an enhanced positioning scheme to decrease the power consumption during the attackers positioning procedure. The main idea is to detect whether the communication between the mobile beacon and each of the static beacons violates the communication properties. The mobile beacon can localize the attacker as the center of its communication area which can be estimated by determining the intersection point of the chords’ perpendicular bisector. Also, the localization accuracy of our proposed scheme is independent of the density of beacon nodes. The main contributions of this paper can be summarized as follows.

• (i)

We propose a novel wormhole attacker detection scheme based on the mobile beacon and the successful detection probability is also theoretically analyzed.

(ii)

We propose a basic positioning scheme to accurately localize the wormhole attacker by estimating the center of the attacker's communication area.

(iii)

We further propose an enhanced positioning scheme for the attackers positioning to decrease the power consumption.

(iv)

We conduct simulations to illustrate the effectiveness of the proposed wormhole attackers detection and positioning schemes.

The rest of this paper is organized as follows. In Section 2, we discuss the existing wormhole attack detection and secure localization schemes. Section 3 presents the system model, including the network model and attack model. In Section 4, we propose the wormhole attacker detection and positioning schemes. The performance evaluation is conducted in Section 5. Section 6 concludes this paper.

2. Related Work

Wormhole attack detection has been a hot research topic during the last decade and lots of schemes have been proposed. In [3], the “packet leashes” mechanism is proposed to use geographical and temporal leashes to detect whether or not the packets are attacked by wormhole attacks. The wormhole detection approach in [4] is based on the end-to-end location information. Another set of wormhole attack preventing techniques [5–7] use the round-trip time of packets as a measurement to detect whether a packet travels via the wormhole link or not. In [8], a “diameter” feature based on the local map is used to detect abnormalities caused by wormholes. LiteWorp [9] makes use of two-hop neighborhood information of the stationary network to reject the packets relayed by the wormhole attacks. MobiWorp [10] uses a secure central authority to isolate the attackers globally after they are detected.

As the wormhole attack dramatically changes the network topology, the network topology information can be used to detect the existence of the wormhole attacks. Wang et al. [11] propose to detect wormhole attacks by visualizing the entire network topology with some anomalies, which is caused by the wormhole attacks. The scheme in [12] uses the network connectivity information to detect wormhole attacks based on the observation that the number of independent neighbors of two nonneighboring nodes is upper bounded. Another connectivity-based wormhole detection approach is proposed in [13] which is robust to different communication models and energy efficient. A topological approach is proposed in [14] to detect the wormhole attacks. In [15], a localized algorithm that detects the wormhole attacks directly using the connectivity information implied by the underlying communication graph is designed, and it requires no specialized hardware, which makes it practical in the real-world scenarios. By detecting whether the communication violates the properties, some novel wormhole detection schemes are proposed in [2, 16, 17].

However, all the above wormhole attack detection schemes cannot localize the attackers, which motivate us to propose the wormhole attackers detection and positioning scheme in this paper. Our proposed scheme can achieve a higher detection probability with a satisfied attackers positioning accuracy.

3. System Model

3.1. Network Model

In this paper, we consider a WSN consisting of three types of nodes: mobile beacon, static beacons, and sensors. The mobile beacon is a node with a GPS device which moves around the network to conduct some special tasks, such as detecting the wormhole attacks. The static beacons are the nodes with fixed locations which can obtain their coordinates in advance by manual deployment or via GPS devices. The sensors are stationary nodes in the network that initially do not know their locations. All the nodes in the network have the same transmission range, denoted as R, and we assume that there is no packet loss during the communication between any two neighboring nodes. Note that our proposed scheme can be extended to the general scenario where packet loss exists. Each of the nodes has a unique ID in the network and all of them can cooperate with each other to realize WSNs applications, such as self-localization, target tracking, and data gathering.

3.2. Attack Model

A hostile environment is considered, in which the deployed WSN will be attacked by the wormhole attacks. A wormhole attack is typically launched by two external attackers, which collude with each other to disrupt the network's functionality. In the wormhole attack, one attacker sniffs packets at one point in the network and forwards these packets to the other attacker via a wormhole link, which will immediately broadcast them to its neighboring nodes. The communication range between the attackers and the nodes is also assumed to be R. However, the communication between two colluding attackers is considered to be symmetrical and not limited to the transmission range R since the wormhole link may be based on some certain communication technique, such as the wired communication. For simplicity, we assume that the distance between each pair of wormhole attackers is larger than $\mathrm{2}R$ ; that is, each pair of wormhole attackers has no communication overlapping with each other. And also, each node in the network is assumed to be covered by at most one attacker.

We denote the mobile beacon, static beacons, sensors, and attackers as $MB$ , B, S, and A, respectively. We also denote a disk centered at u with radius R as $D_R(u)$ . For example, $D_R(B_{\mathrm{1}})$ indicates the communication area of static beacon $B_{\mathrm{1}}$ .

4. Wormhole Attacker Detection and Positioning

In this section, we will first propose the wormhole attacker detection scheme based on the mobile beacon, the detection probability of which will be theoretically analyzed. After that we will propose the wormhole attacker positioning schemes including the basic scheme and enhanced scheme, which can accurately localize the wormhole attackers.

4.1. Wormhole Attacker Detection Scheme

4.1.1. Communication Properties

Before proposing the wormhole attacker detection scheme, we firstly introduce two communication properties, which were proposed in [2] and will be the basis of the detection scheme in this paper.

Packet Uniqueness Property. A node normally cannot receive more than one copy of the same message from any of its neighbors.

Transmission Constraint Property. A node normally cannot communicate with nodes outside its transmission range.

In WSNs, the nodes may need to communicate with its neighbors to accomplish some tasks, and the communication in which should follow the above properties. For example, when a node sends a request message to one of its neighbors to get some information, such as the sensed temperature, it is considered to be normal that this neighbor sends a reply message to the sender for only once if there is no necessity of retransmission. Also, if two nodes are out of the transmission range of each other, it is considered to be normal that the packets from one of them cannot be directly received by the other.

4.1.2. Wormhole Attacker Detection Procedure

If a wormhole attack exists to disrupt the network's functionality, the packet uniqueness property and transmission constraint property may be violated by the nodes' communication. As shown in Figure 2, there are several nodes covered by the wormhole attack; that is, $MB,B_{\mathrm{1}}\in D_R(A_{\mathrm{1}})$ and $B_{\mathrm{2}},B_{\mathrm{3}}\in D_R(A_{\mathrm{2}})$ . The distance between $B_{\mathrm{1}}$ and $B_{\mathrm{2}}$ is shorter than R and the distance between $B_{\mathrm{1}}$ and $B_{\mathrm{3}}$ is longer than R. When $B_{\mathrm{1}}$ sends a request message to its neighbors, every node which receives the request message will send a reply message to $B_{\mathrm{1}}$ . The reply message from $B_{\mathrm{2}}$ will arrive at $B_{\mathrm{1}}$ twice, one directly from $B_{\mathrm{2}}$ to $B_{\mathrm{1}}$ since their distance is shorter than R and the other via the path $B_{\mathrm{2}}\to A_{\mathrm{2}}\to A_{\mathrm{1}}\to B_{\mathrm{1}}$ . Thus, it violates the packet uniqueness property. Although $B_{\mathrm{3}}$ is out of the transmission range of $B_{\mathrm{1}}$ , it can also receive the request message via the path $B_{\mathrm{1}}\to A_{\mathrm{1}}\to A_{\mathrm{2}}\to B_{\mathrm{3}}$ . Similarly, the reply message from $B_{\mathrm{3}}$ can also be received by $B_{\mathrm{1}}$ . Since the distance between $B_{\mathrm{1}}$ and $B_{\mathrm{3}}$ is longer than R, their communication violates the transmission constraint property.

Figure 2

Communication procedure among the nodes under the wormhole attack.

To detect the wormhole attackers in the network, we can use a mobile beacon to detect whether the communication between itself and each of its neighboring static beacons violates the above communication properties. The wormhole attackers detection procedure is as follows.

• (i)

The mobile beacon moves in the network with some direction and step length and then stops to get its current location using GPS. The details of the mobile beacon's mobility model including the moving direction and step length will be discussed in the wormhole attackers positioning scheme.

(ii)

At each stopping location, the mobile beacon broadcasts a request message Req to its neighboring static beacons. Each static beacon who receives the request message will immediately reply a Rep message, including its ID and coordinate, to the mobile beacon.

(iii)

When receiving the Rep message from the static beacon, the mobile beacon will check the receiving times of the Rep from each of the static beacons. If it receives a Rep message from a static beacon more than once, it can determine that there is a wormhole attacker within its transmission range.

(iv)

If the mobile beacon receives the Rep message from each of the static beacons only once, it can then calculate the Euclidean distance between itself and each of them since the received Rep message includes the replier's coordinates. If the transmission constraint property is violated, it can determine that there is a wormhole attacker within its transmission range.

(v)

If nothing abnormal is detected, the mobile beacon will move to next location and perform the above wormhole attacker detection scheme until it finishes the detection of the whole network.

4.1.3. Analysis of Wormhole Attacker Detection Probability

By carefully designing the mobility model of the mobile beacon, we can guarantee that the mobile beacon will move across the communication area of each attacker. Then we can get the following theorem.

Theorem 1.

The mobile beacon can detect the existence of the wormhole attack if at least one static beacon lies in the transmission range of either of the two attackers.

Proof.

Without loss of generality, we assume that there is only a static beacon $B_{\mathrm{1}}$ in the transmission range of attacker $A_{\mathrm{1}}$ , that is, $B_{\mathrm{1}}\in D_R(A_{\mathrm{1}})$ , and no static beacon exists in the transmission range of $A_{\mathrm{2}}$ . When the mobile beacon moves inside $D_R(A_{\mathrm{2}})$ and broadcasts a Req message, it can receive a Rep message from $B_{\mathrm{1}}$ via the wormhole link. If the distance between the mobile beacon and $B_{\mathrm{1}}$ is longer than R, it can determine that their communication procedure violates the transmission constraint property. Otherwise, if their distance is shorter than R, the mobile beacon will receive the Rep message from $B_{\mathrm{1}}$ twice, one directly from $B_{\mathrm{1}}$ to itself and the other via the wormhole link. Thus, it can determine that their communication procedure violates the packet uniqueness property. Therefore, the mobile beacon can detect the wormhole attack. Similarly, if there is only a static beacon $B_{\mathrm{1}}$ in the transmission range of $A_{\mathrm{2}}$ and no static beacon exists in the transmission range of $A_{\mathrm{1}}$ , the mobile beacon can also detect the wormhole attack when it moves inside $D_R(A_{\mathrm{1}})$ .

Based on Theorem 1, we can easily analyze the wormhole attacker detection probability of our proposed scheme. We first consider the scenario with single wormhole attack. The probability that at least one static beacon lies in $D_R(A_{\mathrm{1}})$ (or $D_R(A_{\mathrm{2}})$ ) is denoted as $\text{Pr}(A_{\mathrm{1}})$ (or $\text{Pr}(A_{\mathrm{2}})$ ). Then, the probability that the mobile beacon can successfully detect the wormhole attack, denoted as $\text{Ps}$ , can be calculated as

$$\begin{array}{cc}& \text{Ps}=\mathrm{1}-\overline{\text{Pr}\left(A_{\mathrm{1}}\right)}·\overline{\text{Pr}\left(A_{\mathrm{2}}\right)}.\end{array}$$

(1)

Assume that the deployment of static beacons follows the Poisson distribution with the density ${\rho }_B$ . That is, the probability of k static beacons in an area D can be obtained as $\text{Pr}(N_B=k)=((D{\rho }_B{)}^k/k!)e^{-D{\rho }_B}$ . Thus, we can get $\text{Pr}(A_{\mathrm{1}})=\text{Pr}(A_{\mathrm{2}})=\mathrm{1}-e^{-\pi R^{\mathrm{2}}{\rho }_B}$ . So the probability that the mobile beacon can successfully detect the wormhole attack is

$$\begin{array}{cc}& \text{Ps}=\mathrm{1}-e^{-\pi R^{\mathrm{2}}{\rho }_B}·e^{-\pi R^{\mathrm{2}}{\rho }_B}=\mathrm{1}-e^{-\mathrm{2}\pi R^{\mathrm{2}}{\rho }_B}.\end{array}$$

(2)

For the scenario with multiple wormhole attacks, we consider the detection to be successful only if the mobile beacon can detect all of the wormhole attacks. Since we consider the case that a static beacon can be attacked by at most one attacker, the detection of one of the multiple wormhole attacks is independent of that of other wormhole attacks. Thus, the detection probability that all the wormhole attacks can be successfully detected can be easily obtained as

$$\begin{array}{cc}& \text{Ps}={\left(\mathrm{1}-e^{-\mathrm{2}\pi R^{\mathrm{2}}{\rho }_B}\right)}^n,\end{array}$$

(3)

where n represents the number of wormhole attacks in the network. Note that a wormhole attack is composed of a pair of attackers.

4.2. Wormhole Attackers Positioning Schemes

Based on the above wormhole detection scheme, the mobile beacon can easily detect the wormhole attacks in the network. However, it is not enough to secure a WSN application. Thus, the mobile beacon has to further localize the attackers and then report to the system to eliminate them. In this section, we will first propose a basic positioning scheme which can localize the wormhole attackers accurately. To further reduce the power consumption during the positioning procedure, we will then propose an enhanced positioning scheme.

4.2.1. Basic Positioning Scheme

For ease of description, we assume that the WSN is deployed in a rectangular area of $d_x\times d_y\hspace{0.17em}{m}^{\mathrm{2}}$ and the origin of the coordinate plane locates at the left bottom of the area. As shown in Figure 3(a), the mobile beacon can horizontally move from the origin of the coordinate plane towards the right boundary of the area with a constant moving step length $\mathrm{\Delta }{L}_H$ . It will conduct the wormhole attacker detection scheme each time it moves for a distance of $\mathrm{\Delta }{L}_H$ . When the mobile beacon arrives at the right boundary, it can move up for a distance of $\mathrm{\Delta }{L}_P$ and then move horizontally towards the left boundary with a step length of $\mathrm{\Delta }{L}_H$ . Similarly, when the mobile beacon arrives at the left boundary, it will move up for a distance of $\mathrm{\Delta }{L}_P$ and then move horizontally towards the right boundary of the area with a step length of $\mathrm{\Delta }{L}_H$ . Such operations will be conducted until the whole area is completely scanned by the mobile beacon.

Figure 3

Attackers positioning of the basic scheme: (a) the attackers positioning procedure; (b) determination of $\mathrm{\Delta }{L}_P$ .

When the mobile beacon enters the communication area of an attacker, such as A in Figure 3(a), it can detect the existence of the wormhole attack. Then it can save its current location as $v_f=(x_A,y_A)$ . After that it continues to move towards the right boundary and can detect the wormhole attack at $\hspace{0.17em}\hspace{0.17em}B\hspace{0.17em}\hspace{0.17em}$ and $\hspace{0.17em}\hspace{0.17em}C$ . When the mobile beacon arrives at $\hspace{0.17em}\hspace{0.17em}D$ , it cannot detect the wormhole attack anymore, and then it can save its previous location ( $C\hspace{0.17em}\hspace{0.17em}$ in Figure 3(a)) as $v_l=(x_C,y_C)$ . After that the mobile beacon can estimate the line $AC$ as the chord of the attacker's communication area and the attacker should lie on the perpendicular bisector of $AC$ ; that is, the location of the attacker should be $((x_A+x_C)/\mathrm{2},(y_A+y_C)/\mathrm{2}-\sqrt{R^{\mathrm{2}}-(x_A-x_C{)}^{\mathrm{2}}/\mathrm{4}})$ or $((x_A+x_C)/\mathrm{2},(y_A+y_C)/\mathrm{2}+\sqrt{R^{\mathrm{2}}-(x_A-x_C{)}^{\mathrm{2}}/\mathrm{4}})$ . To further determine the actual location of the attacker, it can then move to $((x_A+x_C)/2,(y_A+y_C)/2+R)$ (E in Figure 3(a)) and check whether it can detect the wormhole attack. If yes, it indicates that the attacker lies above line $AC$ , and the mobile beacon will estimate the attacker's location as $((x_A+x_C)/2,(y_A+y_C)/2+\sqrt{R^{\mathrm{2}}-(x_A-x_C{)}^{\mathrm{2}}/\mathrm{4}})$ ; otherwise, the attacker's location is $((x_A+x_C)/2,(y_A+y_C)/2-\sqrt{R^{\mathrm{2}}-(x_A-x_C{)}^{\mathrm{2}}/\mathrm{4}})$ .

Note that the mobile beacon only conducts the wormhole attack detection scheme every step of $\mathrm{\Delta }{L}_H$ , and it cannot exactly determine the intersection points between the chord and the attacker's communication circle. As shown in Figure 3(a), A and C are not exactly on the attacker's communication circle. Thus, we need to carefully design $\mathrm{\Delta }{L}_H$ and $\mathrm{\Delta }{L}_P$ to make the proposed basic attacker positioning scheme feasible. As the value of $\mathrm{\Delta }{L}_H$ determines the localization accuracy of the basic scheme, we can firstly set it as $\mathrm{\Delta }{L}_H=\alpha R$ , where $\mathrm{0}<\alpha <\mathrm{1}$ . Then we have to determine the value of $\mathrm{\Delta }{L}_P$ . As shown in Figure 3(b), when mobile beacon moves from A to C, it will estimate the location of the chord AC's midpoint with a maximum error of $\mathrm{\Delta }{L}_H/\mathrm{2}$ . Assume that the mobile beacon estimates it as $B^{\prime }$ , and then $B{B}^{\prime }\le \mathrm{\Delta }{L}_H/\mathrm{2}$ . To guarantee that the mobile beacon can still detect the wormhole attack when it moves to $((x_A+x_C)/2,(y_A+y_C)/2+R)$ , it must be satisfied that $B^{\prime }F\ge R$ . As $B{B}^{\prime }\le \mathrm{\Delta }{L}_H/\mathrm{2}$ , we can get

$$\begin{array}{cc}& B^{\prime }F=GF+B^{\prime }G\ge \sqrt{R^{\mathrm{2}}-\frac{\mathrm{\Delta }{L}_H^{\mathrm{2}}}{\mathrm{4}}}+B^{\prime }G.\end{array}$$

(4)

Then to guarantee that $B^{\prime }F\ge R$ , we can make $\sqrt{R^{\mathrm{2}}-\mathrm{\Delta }{L}_H^{\mathrm{2}}/\mathrm{4}}+B^{\prime }G\ge R$ . Finally, we can get $B^{\prime }G\ge R-\sqrt{R^{\mathrm{2}}-\mathrm{\Delta }{L}_H^{\mathrm{2}}/\mathrm{4}}$ . Also, to guarantee that the mobile beacon can conduct the wormhole attack for at least once on line $AC$ , it must satisfy that $AC\ge \mathrm{\Delta }{L}_H$ . So $B^{\prime }G=OB\le \sqrt{R^{\mathrm{2}}-\mathrm{\Delta }{L}_H^{\mathrm{2}}/\mathrm{4}}$ . Thus, to guarantee that the mobile beacon can correctly localize the attacker when it moves along AC, it must satisfy that

$$\begin{array}{cc}& R-\sqrt{R^{\mathrm{2}}-\frac{\mathrm{\Delta }{L}_H^{\mathrm{2}}}{\mathrm{4}}}\le B^{\prime }G\le \sqrt{R^{\mathrm{2}}-\frac{\mathrm{\Delta }{L}_H^{\mathrm{2}}}{\mathrm{4}}}.\end{array}$$

(5)

To guarantee that the mobile beacon can move across the attacker's communication range with the condition that $B^{\prime }G\in [R-\sqrt{R^{\mathrm{2}}-\mathrm{\Delta }{L}_H^{\mathrm{2}}/\mathrm{4}},\sqrt{R^{\mathrm{2}}-\mathrm{\Delta }{L}_H^{\mathrm{2}}/\mathrm{4}}]$ , it must satisfy that $\mathrm{\Delta }{L}_P\le \sqrt{R^{\mathrm{2}}-\mathrm{\Delta }{L}_H^{\mathrm{2}}/\mathrm{4}}-(R-\sqrt{R^{\mathrm{2}}-\mathrm{\Delta }{L}_H^{\mathrm{2}}/\mathrm{4}})$ . That is,

$$\begin{array}{cc}& \mathrm{\Delta }{L}_P\le \mathrm{2}\sqrt{R^{\mathrm{2}}-\frac{\mathrm{\Delta }{L}_H^{\mathrm{2}}}{\mathrm{4}}}-R.\end{array}$$

(6)

The previous scheme can localize the attackers accurately when there exists only one wormhole attack. However, if multiple wormhole attacks exist and the attackers are close enough to each other, there may be some problem. For example, as shown in Figure 4, when the mobile beacon node moves from C to D, although it is out of transmission range of attacker $A_{\mathrm{3}}$ , it can still detect the wormhole attack since the communication between itself and $B_{\mathrm{1}}$ violates the communication property. Thus, using the previous scheme, the mobile beacon node will incorrectly estimate the midpoint of the chord of $D_R(A_{\mathrm{3}})$ , leading to inaccurate attackers positioning. To solve this problem, we can use the concept of conflicting nodes, which we borrow from our previous work [18].

Figure 4

Attackers positioning of multiple wormhole attacks using conflicting set.

In this paper, we define the conflicting nodes of the mobile beacon node as the beacon nodes, and the communication between which and the mobile beacon node violates the packet uniqueness property or the transmission constraint property. That is to say, the conflicting nodes of the mobile beacon node are the beacon nodes which communicate with itself via the wormhole link. For example, as shown in Figure 4, when the mobile beacon node arrives at A, it can detect the wormhole attack as it can check that the communication between itself and $B_{\mathrm{2}}$ violates the communication property; thus it will consider $B_{\mathrm{2}}$ as its conflicting node. While it moves to D, it cannot communicate with $B_{\mathrm{2}}$ , but it can still check that the communication between itself and $B_{\mathrm{1}}$ violates the communication property, so it will then consider $B_{\mathrm{1}}$ as its conflicting node.

Thus, when the mobile beacon node enters the communication range of an attacker, we can get the following theorem.

Theorem 2.

When the mobile beacon node enters the area of $D_R(A_{\mathrm{1}})$ , its conflicting nodes are all the beacon nodes inside $D_R(A_{\mathrm{2}})$ , where $A_{\mathrm{1}}$ and $A_{\mathrm{2}}$ are a pair of wormhole attackers.

Proof.

All the beacon nodes inside $D_R(A_{\mathrm{2}})$ can be classified into two sets according to the distance between each of them and the mobile beacon node. For the beacon nodes, the distance between each of which and the mobile beacon node is not larger than R, and the communication between them and the mobile beacon node violates the packet uniqueness property. Thus, the mobile beacon node will consider them as its conflicting nodes. While, for the beacon nodes, the distance between each of which and the mobile beacon node is larger than R, the communication between them and the mobile beacon node violates the transmission constraint property since they can communicate with each other via the wormhole link. Thus, the mobile beacon node will also consider these nodes as its conflicting nodes. While for other beacon nodes outside $D_R(A_{\mathrm{2}})$ , since they cannot communicate with the mobile beacon node via the wormhole link, they will not be considered as the mobile beacon node's conflicting nodes.

Based on Theorem 2, we can get the following corollary.

Corollary 3.

If the mobile beacon node has the same conflicting nodes at two locations, then it is within the communication range of the same attacker.

According to Corollary 3, the mobile beacon node can identify different wormhole attackers easily. For example, as shown in Figure 4, when the mobile beacon node moves to $\hspace{0.17em}\hspace{0.17em}A$ , it will detect the wormhole attack. Furthermore, it will consider $B_{\mathrm{2}}$ as its conflicting node. Then when it moves to $\hspace{0.17em}\hspace{0.17em}B$ , it can still detect the wormhole attack and $B_{\mathrm{2}}$ is also considered as its conflicting node. Thus the mobile beacon node continues to move to C and conducts the corresponding detection. When it moves to D, although it can detect the wormhole attack, it will find that its current conflicting node is different from the previous point; thus it can determine that it moves out the transmission range of the last attacker, that is, $A_{\mathrm{3}}$ . After that it can estimate the line $AC$ as the chord of $D_R(A_{\mathrm{3}})$ and $A_{\mathrm{3}}$ should lie on the perpendicular bisector of $AC$ ; that is, the location of $A_{\mathrm{3}}$ should be $((x_A+x_C)/2,(y_A+y_C)/2-\sqrt{R^{\mathrm{2}}-(x_A-x_C{)}^{\mathrm{2}}/\mathrm{4}})$ or $((x_A+x_C)/2,(y_A+y_C)/2+\sqrt{R^{\mathrm{2}}-(x_A-x_C{)}^{\mathrm{2}}/\mathrm{4}})$ . Then the mobile beacon node can first move to $((x_A+x_C)/2,(y_A+y_C)/2-\sqrt{R^{\mathrm{2}}-(x_A-x_C{)}^{\mathrm{2}}/\mathrm{4}})$ to check whether it can detect the wormhole attack and also whether the conflicting node is still $B_{\mathrm{2}}$ ; if yes, it can determine that the location of $A_{\mathrm{3}}$ is $((x_A+x_C)/2,(y_A+y_C)/2-\sqrt{R^{\mathrm{2}}-(x_A-x_C{)}^{\mathrm{2}}/\mathrm{4}})$ . Otherwise, the location of $A_{\mathrm{3}}$ is $((x_A+x_C)/2,(y_A+y_C)/2+\sqrt{R^{\mathrm{2}}-(x_A-x_C{)}^{\mathrm{2}}/\mathrm{4}})$ .

4.2.2. Enhanced Positioning Scheme

In the basic positioning scheme, when the mobile beacon node moves forward a step, it will conduct the wormhole attack detection, in which it broadcasts a Req message to its neighboring beacon nodes and then waits for the Rep messages from them. Such kind of procedure involves the message exchange between the mobile beacon node and its neighboring beacon nodes, which is energy consuming. In this section, we will propose an enhanced positioning scheme, which can reduce the energy consumption of the positioning procedure.

Since the mobile beacon node moves across the network, it may enter the transmission range of an attacker for more than once. As shown in Figure 5, when the mobile beacon node moves from A to C, it can detect the existence of the wormhole attack after which it can determine the location of the attacker as $((x_A+x_C)/2,(y_A+y_C)/2+\sqrt{R^{\mathrm{2}}-(x_A-x_C{)}^{\mathrm{2}}/\mathrm{4}})$ . Then it can save the currently estimated location of the attacker into the set $X_A$ . When the mobile beacon node moves out of the transmission range of the current attacker, it will first check whether the next location lies in the transmission range of any of the attackers in $X_A$ . If yes, it can ignore this location and check next location until the one which is outside the transmission range of each of the attackers in $X_A$ , and then it can move to that location and conduct the wormhole attack detection. Note that the attackers in $X_A$ have already been positioned by the mobile beacon node; thus it will not affect the attacker positioning by ignoring the detection procedures at such locations. For example, as shown in Figure 5, when the mobile beacon node moves to $\hspace{0.17em}\hspace{0.17em}D$ , it detects that there is no wormhole attack, and then it decides to move to next location, which is $(x_D+\mathrm{\Delta }{L}_H,y_D)$ . However, it can detect that the distance between next location and $((x_A+x_C)/2,(y_A+y_C)/2+\sqrt{R^{\mathrm{2}}-(x_A-x_C{)}^{\mathrm{2}}/\mathrm{4}})$ , which is estimated as the location of an attacker and is saved in $X_A$ , is shorter than R, and then it will not conduct wormhole attack detection at this location. Similarly, the mobile beacon node will check the next several locations and find that E is not within the transmission range of each of the attackers in $X_A$ . Thus it will directly move to $\hspace{0.17em}\hspace{0.17em}E\hspace{0.17em}\hspace{0.17em}$ and conduct the wormhole attack detection there. By using such strategy, some unnecessary locations can be found, at which the energy-consuming wormhole attack detection procedure will not be conducted. Moreover, the enhanced positioning scheme will not degrade the attackers positioning performance.

Figure 5

The procedure of the enhanced attackers positioning scheme.

5. Performance Evaluation

In this section, we present the simulation results to demonstrate the effectiveness of the proposed wormhole attackers detection and positioning scheme. We compare the proposed scheme with the label-based scheme proposed in [2] as the detection scheme of the label-based scheme is similar to our proposed scheme and it can also estimate the locations of the wormhole attackers. In the simulation, a WSN is randomly deployed in a $\mathrm{1}\times \mathrm{1}\hspace{0.17em}\text{k}{\text{m}}^{\mathrm{2}}$ region and the transmission range of each node is set as $\mathrm{150}\hspace{0.17em}\text{m}$ .

Figure 6 illustrates the comparison of the wormhole attack detection probability of our proposed scheme between the simulation and the theoretical model under single wormhole attack. We vary the number of beacon nodes from 10 to 30; that is, the density of the beacon nodes varies from $\mathrm{1}{\mathrm{0}}^{-\mathrm{5}}$ to $\mathrm{3}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{5}}$ . The results show that the theoretical model matches the simulation quite well, which validates the correctness of the theoretical analysis on the wormhole attack detection probability.

Figure 6

Wormhole attack detection probability: simulation versus theoretical model.

Figure 7 illustrates the wormhole detection probability of the proposed scheme and the label-based scheme when there is only a wormhole attack in the network. In the label-based scheme, the wormhole attack can be detected by checking whether the communications between the beacon nodes violate the properties and the precondition is that there exists at least one beacon node within the communication range of each of the attackers. In our proposed scheme, we select $\mathrm{\Delta }{L}_H=\mathrm{0.1}R=\mathrm{15}\hspace{0.17em}\text{m}$ , and $\mathrm{\Delta }{L}_P$ is set as the maximum value corresponding to the selected $\mathrm{\Delta }{L}_H$ ; that is, $\mathrm{\Delta }{L}_P=\mathrm{2}\sqrt{R^{\mathrm{2}}-\mathrm{\Delta }{L}_H^{\mathrm{2}}/\mathrm{4}}-R=\mathrm{149.6}\hspace{0.17em}\text{m}$ , which can minimize the power consumption introduced by the mobile beacon. It shows that our proposed scheme can achieve a much higher detection probability than the label-based scheme. And when the number of beacon nodes equals 20, that is, there are 1.4 beacons in the transmission range of the attacker in average, the detection probability of our proposed scheme is larger than 95%. Overall, our proposed scheme outperforms the label-based scheme.

Figure 7

Wormhole detection probability of the proposed scheme and the label-based scheme with only single wormhole attack.

Figure 8 illustrates the wormhole detection probability of our proposed scheme with different number of wormhole attacks in which the settings of $\mathrm{\Delta }{L}_H$ and $\mathrm{\Delta }{L}_P$ are the same with that in Figure 7. It shows that when the number of wormhole attacks increases, the detection probability will decrease, which is consistent with (3). However, the detection probability is relatively high when the number of beacons is larger than 20.

Figure 8

The effects of the number of wormholes on the detection probability.

Figure 9 illustrates the wormhole attacker positioning error of our proposed scheme and the label-based scheme in which the settings of $\mathrm{\Delta }{L}_H$ and $\mathrm{\Delta }{L}_P$ are the same with that in Figure 7. In the label-based scheme, the attacker will be estimated as the centrality of all the beacons within its transmission range. Note that the attackers positioning performance of the basic scheme and the enhanced scheme is the same; here we do not differentiate between them. It shows that our proposed scheme can achieve a much higher positioning accuracy than the label-based scheme. Furthermore, the positioning accuracy of the label-based scheme depends on the number of beacons, while our proposed scheme obtains a stable positioning accuracy with different number of beacons.

Figure 9

The average positioning error of our proposed scheme and the label-based scheme.

Figure 10 illustrates the effects of the moving step lengths $\mathrm{\Delta }{L}_H$ and $\mathrm{\Delta }{L}_P$ on the attacker positioning accuracy of our proposed scheme (here we also do not differentiate between the basic scheme and the enhanced scheme since their positioning performance is the same). We vary the value of $\mathrm{\Delta }{L}_H$ from $\mathrm{0.1}R$ to $\mathrm{0.5}R$ with an increment of $\mathrm{0.1}R$ . And similarly, to minimize the power consumption introduced by the mobile beacon node, $\mathrm{\Delta }{L}_P$ is set as the maximum value corresponding to each $\mathrm{\Delta }{L}_H$ ; that is, $\mathrm{\Delta }{L}_P=\mathrm{2}\sqrt{R^{\mathrm{2}}-\mathrm{\Delta }{L}_H^{\mathrm{2}}/\mathrm{4}}-R$ . It shows that the increase of moving step length will degrade the attacker positioning accuracy. Furthermore, even when $\mathrm{\Delta }{L}_P=\mathrm{0.5}R$ , the attacker positioning error of our proposed scheme is still less than the label-based scheme.

Figure 10

The effects of mobile beacon node's moving step length on the attacker positioning accuracy.

Figure 11 illustrates the comparison of the detection times between the basic scheme and the enhanced scheme under different number of wormholes. The detection times here mean the total times that the mobile beacon node stop to conduct the wormhole attack detection in the whole network. Since the energy consumption in the proposed scheme mainly occurs during the wormhole attack detection, which requires the nodes to exchange messages, we can analyze the energy consumption of the scheme by directly evaluating the detection times. We adopt $\mathrm{\Delta }{L}_P=\mathrm{0.3}R$ in Figure 11. We can observe that the number of wormholes does not affect the detection times of the basic scheme, while the increase of the number of wormholes will reduce the detection times of the enhanced scheme. Also, it shows that the proposed enhanced scheme has fewer detection times than the basic scheme, which indicates that it consumes less power than the basic scheme.

Figure 11

The comparison of the detection times between the basic scheme and the enhanced scheme.

The effects of the moving step length $\mathrm{\Delta }{L}_H$ and $\mathrm{\Delta }{L}_P$ on the detection times of the proposed enhanced scheme are illustrated in Figure 12. The curves in Figure 12 show that the increase of moving step length, including $\mathrm{\Delta }{L}_H$ and $\mathrm{\Delta }{L}_P$ , can reduce the detection times; that is, it can reduce the introduced energy consumption. As the increase of the moving step length can also reduce the attackers positioning accuracy as shown in Figure 10, a tradeoff between the positioning accuracy and the energy consumption should be well balanced.

Figure 12

The effects of mobile beacon node's moving step length on the detection times of the proposed enhanced scheme.

6. Conclusions

In this paper, we proposed a novel wormhole attackers detection and positioning scheme, which can not only detect the existence of wormhole attacks, but also localize the attackers with a high accuracy for the system to eliminate them out of the network. The main idea is to detect whether the communication between the mobile beacon and the static beacons violates the communication properties and then the attacker can be localized as the center of its communication disk by finding the intersection point of the chords' perpendicular bisector. The simulation results illustrated that our proposed scheme can obtain a high wormhole attack detection probability together with a high accuracy for localizing the attackers.