BRS-Based Robust Secure Localization Algorithm for Wireless Sensor Networks

Abstract

Localization is the key supporting technology for wireless sensor networks (WSNs). Security and accuracy are the premise of the localization application. Real-world applications of wireless sensor networks are often subject to a variety of adverse circumstances interference, and the localization performance is seriously affected. In this paper, we propose a BRS-based robust secure localization (BRSL) algorithm in order to reduce the impact of the malicious attackers in WSNs. The BRSL method includes two phases. In the first stage, the trust evaluation framework is established on the basis of beta reputation system. In the second phase, we employ the weighted Taylor-series least squares method to estimate the coordinates of sensor nodes. Simulation results demonstrate that the proposed algorithm is robust and effective.

1. Introduction

Wireless sensor networks (WSNs) are based on the technology of sensor, wireless communication, tiny embedded devices, and distributed computing. They exchange information with the environment through sensors and implement the function of collecting and dealing with data. Wireless sensor networks have been widely used in the fields of environmental monitoring, target tracking, military applications, disaster management, and so forth [1–3].

Self-localization technology of nodes is the prerequisite and basis for the application of wireless sensor networks, especially the position information that is needed for the perceived data. Node localization of WSNs is to determine the positions of normal nodes based on the positions of beacon nodes and the constraint relations between normal and beacon nodes. Positions or coordinates of normal nodes are unknown. Beacon nodes usually get their positions or coordinates through global positioning system (GPS) modules or by manual deployments. Being an essential support technology of wireless sensor networks, node localization has got more and more attention in the recent years [4–10].

Most localization methods depend on measuring the distances or hops between normal and beacon nodes to obtain the coordinates of normal nodes. In many typical localization algorithms [11–13], the coordinates of beacon nodes are generally assumed to be completely correct without any disturbs of adverse factors, and the normal nodes can use beacon information in security. However, in the actual hostile situations, some malicious nodes may intrude into sensor networks. They pretend to be true beacon nodes or attack other anchor nodes and make them declare false coordinates [14, 15]. The false coordinates or distance estimation will cause a major localization error for normal sensor nodes [16]. In this case, some methods should be explored to eliminate or reduce the adverse influence caused by malicious beacon nodes and ensure safe localization in wireless sensor networks.

In this paper, we develop a BRS-based robust secure localization (BRSL) algorithm for solving the node self-localization problem in the case of malicious nodes existence. In BRSL, normal sensor node first observes the anchor nodes in its communication range and evaluates the trust values of these anchor nodes. Specially, the concepts of the beta reputation system are employed to deal with the uncertain factors in trust evaluation. Then, each anchor node obtains a final trust value, and sensor nodes compare the final trust values of anchor nodes in their multihop communication range with the stored threshold. Finally, the normal sensor nodes utilize the trustful anchor nodes to estimate their coordinates. All the above operations can be carried out by each node. The method is a completely distributed localization approach. Through simulations, we demonstrate that the BRSL method can efficiently reduce the influence of malicious attackers in WSNs.

The remainder of the paper is organized as follows: Section 2 introduces related works on secure localization algorithms. Section 3 presents the network model, attack model, and related definitions. Section 4 provides the details of the BRS-based robust secure localization (BRSL) algorithm. Section 5 presents the simulation results. Section 6 concludes the paper.

2. Related Works

Alfaro et al. [17] consider the localization security of sensor nodes under limited trust anchor nodes. It introduces three algorithms to enable the sensor nodes to determine their positions, but it would fail when the malicious anchor nodes are in colluding conditions.

Liu et al. [18] propose two secure localization algorithms. One is attack-resistant minimum mean square estimation, which excludes malicious anchor nodes by the consistency check. The other is voting-based location estimation. The algorithms are difficult to work for the malicious anchor nodes in colluding conditions.

Zhu et al. [19] propose an attack detection module which can detect compromised beacons and provide a localization service in terms of bounded estimation error by secure localization module, but it mainly concentrates on the one-hop localization.

Liu et al. [20] present a secure localization mechanism that detects malicious anchor nodes claiming fake positions. It uses redundant anchor nodes instead of normal nodes in the sensing field to verify malicious anchors. The method relies on a centralized base station for the detection.

Li et al. [21] introduce a secure scheme “Bilateration” which is derived from multilateration. It calculates the weight of anchor nodes and decides which anchor nodes are malicious. After ignoring the coordinates caused by compromised nodes, it uses the average value of the left candidate positions as the estimated location of the sensor node, but it mainly focuses on the one-hop localization.

3. Preliminaries

3.1. Network Model

We consider a network consisting of two types of nodes, namely, anchor nodes and sensor nodes. The anchor nodes are specially equipped and aware of their coordinates after deployment. The sensor nodes, whose positions are yet to be discovered, estimate their locations by measuring distances to neighboring anchor nodes. All nodes are randomly distributed in a 2D spatial region. Every node has a unique identity (ID). The transmission range or ranging radius of each node is R. Every node is capable of measuring the distance to any of its immediate neighbors. The ranging error e follows a Gaussian distribution $N (u, λ^{2})$ , where the mean u is 0 and the standard deviation λ is within a threshold. Measurement error e is bounded by $| e_{i} | \leq e_{\max}$ , and the maximum physical inaccuracy $e_{\max}$ can be obtained experimentally. In multihop localization, each anchor node broadcasts a message that carries its declared position to its one-hop neighbors. Then, the message is propagated in the network in a controlled flooding manner. When a sensor node obtains three or more anchor messages, the sensor node can estimate its location by the localization algorithm.

3.2. Attack Model

We assume that the WSN is in a hostile environment, that is, there are malicious attackers in the network. The attackers attack the anchor nodes in order to make them declare dishonest coordinates. When an anchor node is attacked and broadcasts erroneous locations, we call it malicious anchor node. The nodes claiming actual coordinates are called benign anchor nodes. We consider an adversarial environment where the malicious anchor nodes are in noncolluding scenario or colluding scenario. If the malicious anchor nodes are noncolluding, they cannot know whether other anchor nodes are malicious or not. They can only fake their own declared locations to affect the localization process. While the malicious anchor nodes are colluding, they can detect whether other anchor nodes are the same type, and each pair of colluding malicious anchor nodes can revise the measure distance between them by changing their declared locations.

As shown in Figure 1, when a sensor node M gets enough measurement distances $d_{m i}$ ( $i = 1, 2, \dots, k$ ), where $k \geq 3$ , to anchor nodes $A_{i}$ , a system of the Euclidean equations can be set up:

\begin{matrix} {∥ X_{m} - X_{1} ∥}_{2} = d_{m 1} \\ {∥ X_{m} - X_{2} ∥}_{2} = d_{m 2} \\ ⋮ \\ {∥ X_{m} - X_{k} ∥}_{2} = d_{m k}, \end{matrix}

(1)

where

X_{m} = {[x_{m}, y_{m}]}^{T}

is M's coordinates that need to be estimated and

X_{i} = {[x_{i}, y_{i}]}^{T}

is anchor node

A_{i}

's declared position.

Figure 1

Node localization with malicious anchor node.

If the anchor node $A_{1}$ is attacked, it will become a malicious anchor node $A_{1}^{'}$ with fake coordinates. When M utilizes $A_{1}^{'}$ to compute its position, its estimated position $M^{'}$ will deviate far from its physical position, and its location accuracy will be very low.

3.3. Related Definitions

To be convenient, some necessary definitions are given in the following.

(i)

Measurement distance: node i is in the communication radius of node j. The physical measurement distance from i to j (through RSSI, TDOA, etc.) is called measurement distance.

(ii)

The Euclidean distance: the distance between the declared coordinates of two anchor nodes i and j, that is,

\begin{matrix} d_{i j} = {∥ X_{i} - X_{j} ∥}_{2} = \sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2}}, \end{matrix}

(2)

where

X_{i} = {[x_{i}, y_{i}]}^{T}

and

X_{j} = {[x_{j}, y_{j}]}^{T}

denote, respectively, the declared coordinates of anchors i and j.

(iii)

Multihop communication range: the range that a node's propagation packet can reach through multihop forwarding.

(iv)

Multihop count: the hops count of the shortest path between a pair of nodes. For example, if the shortest path between nodes i and j passes T nodes (including i and j), the multihop count of nodes i and j is $HOP_{i j} = T - 1$ .

4. BRS-Based Robust Secure Localization (BRSL) Algorithm

In BRSL method, every sensor node has the detecting function. The sensor node examines each of the anchor nodes that are available to it and evaluates the reliability of each anchor node according to the geometric relationship among anchor nodes. After the sensor node obtains the final trust values of each anchor node, a weighted Taylor-series least squares method is utilized to compute the sensor nodes' coordinates. In general, the BRSL method includes two main phases: trust evaluation of anchor nodes and the localization of sensor nodes.

4.1. Trust Evaluation of Anchor Nodes

In this subsection, we employ the concepts of the beta reputation system [22] to construct the trust evaluation framework of anchor nodes. In contrast to most other intuitive reputation systems, the beta reputation system has a firm basis on the theory of statistics, that is, the beta probability density function. The beta distribution B $(a, β)$ can be expressed by using the gamma function as

\begin{matrix} f (x ∣ α, β) = \frac{Γ (α + β)}{Γ (α) Γ (β)} x^{α - 1} {(1 - x)}^{β - 1}, \end{matrix}

(3)

where

0 < x < 1

α > 0

β > 0

, and

Γ (a)

is the gamma function.

The gamma function [23] (represented by the capital Greek letter $Γ$ ) is an extension of the factorial function, with its argument shifted down by 1, to real and complex numbers. If n is a positive integer, we get the formula $Γ (n) = (n - 1)$ . If z is a complex number, we get the formula $Γ (z) = \int_{0}^{⋈} (t^{(z - 1)} / e^{t}) d t$ , where the real part of z must be larger than zero $(R e (z) > 0)$ . The gamma function is applicable in the fields of probability and statistics. It is also a component in various probability-distribution functions.

The beta reputation system consists of two elements $(α, β)$ that can be used separately or in combination to provide a flexible framework for reputation services of WSNs applications. We use the beta reputation system to establish the trust evaluation framework of anchor nodes. In the network, anchor nodes have two types: benign anchor nodes and malicious anchor nodes. And the two elements $(α, β)$ of beta reputation system are the most appropriate parameters here to judge the anchor nodes. The probability expectation value of the beta distribution is given by

\begin{matrix} E (x) = \frac{α}{α + β}, \end{matrix}

(4)

and the variance is

\begin{matrix} Var (x) = \frac{α β}{{(α + β)}^{2} (α + β + 1)} . \end{matrix}

(5)

In the network, every anchor node has a unique ID, and the sensor node is assumed to have the detecting function. We utilize the beta reputation system to detect the malicious anchor nodes. The detecting process is considered with two possible outcomes (benign anchor node and malicious anchor node). Let $(a + 1)$ be the observed outcome number of benign anchor nodes, and let $(b + 1)$ be the observed outcome number of malicious anchor nodes. Then, we have a beta function expressed as $f (x ∣ (a + 1), (b + 1))$ , where x denotes the benign anchor node. The observed number of benign anchor nodes and malicious anchor nodes is used in the beta function to estimate the probability of anchor nodes to be benign ones, which equals to the expectation value of x. As we do not know whether the anchor nodes are benign or not at the beginning, we initially assume all anchor nodes to be benign ones.

Let $R e p_T$ denotes the reputation of anchor nodes and $R e p_T$ ~ $B (a + 1, b + 1)$ . Let $T r u_T$ denotes the trust value of the anchor node. From the beta reputation system, we know that the expectation value of $R e p_T$ is equal to $T r u_T$ , that is, $E (R e p_T) = T r u_T$ . Assume that there are $N_{1} + N_{2}$ anchor nodes and $N_{3}$ sensor nodes randomly deployed in the network. Assume n (n ≤ $N_{1} + N_{2}$ ) anchor nodes ( $A_{1}, A_{2}, \dots, A_{n}$ ) are available to an arbitrary sensor node $M_{j}$ . We deploy the network Q times in total. The detail of the detecting process is given as follows. (1)

Compute $a_{i}$ and $b_{i}$ through the geometric relationship among anchor nodes. The values of $a_{i}$ and $b_{i}$ are set to 0 initially. The value of $d_{i j}$ is the Euclidean distance between $A_{i}$ and $A_{j}$ , and ${d_{i j}^{'}}^{}$ denotes the measurement distance between $A_{i}$ and $A_{j}$ (if $A_{i}$ and $A_{j}$ are neighbors).

(a)

If inequality $| d_{i j} - d_{i j}^{'} | \leq$ $e_{\max}$ or 0 < $d_{i j}$ < $2 R$ is satisfied, let $a_{i}^{j} = 1$ . Otherwise, let $a_{i}^{j} = 0$ .

(b)

If inequality $| d_{i j} - d_{i j}^{'} |$ > $e_{\max}$ or $d_{i j}$ > $2 R > 0$ is satisfied, let $b_{i}^{j} = 1$ . Otherwise, let $b_{i}^{j} = 0$ .

For example, Figure 2 shows the geometric relationship among anchor nodes, in which $A_{i}$ ( $i =$ $1, 2, \dots, 6$ ) represents the anchor nodes and $M_{j}$ ( $j =$ $1, 2, \dots, 5$ ) represents the sensor nodes. Anchor node $A_{2}$ is attacked, and $A_{2}^{'}$ is the declared position of $A_{2}$ . As anchor node $A_{3}$ is not the neighbor of $A_{2}$ , we can only obtain the Euclidean distance $d_{23}$ between them. A set of inequalities can be set up: $| d_{12} - d_{12}^{'} |$ > $e_{\max}$ , $| d_{14} - d_{14}^{'} |$ ≤ $e_{\max}$ , $| d_{15} - d_{15}^{'} |$ ≤ $e_{\max}$ , $| d_{16} - d_{16}^{'} |$ ≤ $e_{\max}$ , and $0 < d_{23} < 2 R$ . Sensor nodes $M_{1}$ and $M_{3}$ are in anchor node $A_{1}$ 's communication range. Therefore, we can get $a_{1}^{1} = 2, b_{1}^{1} = 1 and a_{1}^{3} = 2, b_{1}^{3} = 0$ . (2)

Compute the trust value of anchor node $A_{i}$ in each network deployment.

(a)

Assume that m (m≤ $N_{3}$ ) sensor nodes ( $M_{1}, M_{2}, \dots, M_{m}$ ) are available to anchor node $A_{i}$ . These m sensor nodes utilize step (1) to detect anchor node $A_{i}$ . The observed number of anchor node $A_{i}$ to be a benign one is

\begin{matrix} a_{i}^{'} + 1 = \sum_{j = 1}^{m} a_{i}^{j} + 1 \end{matrix}

(6)

and the observed number of anchor node

A_{i}

to be a malicious one is

\begin{matrix} b_{i}^{'} + 1 = \sum_{j = 1}^{m} b_{i}^{j} + 1 . \end{matrix}

(7)

(b)

The $R e p_T_{A_{i} p} ~ B (a_{i}^{'} + 1, b_{i}^{'} + 1)$ . The trust value of anchor node $A_{i}$ is

\begin{matrix} T r {u_T}_{A_{i} p} = E (R e p_T_{A_{i} p}) = \frac{a_{i}^{'} + 1}{a_{i}^{'} + b_{i}^{'} + 2}, \end{matrix}

(8)

and the variance of anchor node

A_{i}

\begin{matrix} σ_{A_{i} p} = \frac{(a_{i}^{'} + 1) \times (b_{i}^{'} + 1)}{{(a_{i}^{'} + b_{i}^{'} + 2)}^{2} (a_{i}^{'} + b_{i}^{'} + 3)} . \end{matrix}

(9)

(3)

Compute the trust value of anchor node $A_{i}$ after the Q times network deployment. Let p denotes the current deployment time. Repeat step (1) and step (2) until $p > Q$ . The final trust value of anchor node $A_{i}$ is

\begin{matrix} T r {u_T}_{A_{i}} = \frac{(\sum_{p = 1}^{Q} T r u_T_{A_{i} p})}{Q}, \end{matrix}

(10)

and the final variance of anchor node

A_{i}

\begin{matrix} σ_{A_{i}} = \frac{(\sum_{p = 1}^{Q} σ_{A_{i} p})}{Q} . \end{matrix}

(11)

(4)

Judge whether anchor node $A_{i}$ is a benign anchor node.

(a)

After the anchor node $A_{i}$ obtains the final trust value $T r u_T_{A_{i}}$ , it broadcasts $T r u_T_{A_{i}}$ to the network in a multihop flooding manner. The sensor nodes store the final trust values they obtained, based on which they can decide whether $A_{i}$ is a benign anchor node.

(b)

The sensor nodes compare the $T r u_T_{A_{i}}$ that they received from step (3) with threshold ∇. If $T r u_T_{A_{i}}$ ≥∇, sensor nodes will consider anchor node $A_{i}$ as a benign anchor node and utilize $A_{i}$ in the localization phase. If $T r u_T_{A_{i}}$ <∇, sensor nodes will take anchor node $A_{i}$ as a malicious anchor node, and $A_{i}$ will be revoked before the localization stage.

Figure 2

Geometric relationship among anchor nodes.

The determination of threshold ∇ depends on the final trust value of each anchor node. The threshold ∇ is defined as follows

\begin{matrix} \nabla = \sum_{q = 1}^{N_{1} + N_{2}} ((\frac{σ_{q}}{\sum_{q = 1}^{N_{1} + N_{2}} σ_{q}}) \times T r u_T_{q}), \end{matrix}

(12)

where

N_{1} + N_{2}

is the total number of anchor nodes, q is the ID of anchor node, and

σ_{q}

is the final variance of anchor node q.

From the above steps, we will get the trust evaluation of anchor nodes. The situation we investigated in this paper is that the percentage of malicious anchor nodes is less than half of the number of anchor nodes. When the malicious anchor nodes are noncolluding, they will not cooperate with each other. Therefore, it is hard for these malicious anchor nodes to obtain high value of $a_{i}^{'}$ . As the number of malicious anchor nodes is less than that of benign ones, the colluding malicious anchor nodes will be given more value on ${b_{i}^{'}}^{}$ . When malicious anchor nodes are cooperated, some malicious anchor nodes may obtain more value on ${a_{i}^{'}}^{}$ than ${b_{i}^{'}}^{}$ , but such nodes are very few. Generally, $a_{i}^{'}$ is smaller than ${b_{i}^{'}}^{}$ for malicious anchor nodes, and ${a_{i}^{'}}^{}$ is bigger than ${b_{i}^{'}}^{}$ for benign anchor nodes. Therefore, most benign anchor nodes' trust values are larger than that of malicious anchor nodes in each network deployment.

Formula (8) shows that the bigger ${a_{i}^{'}}^{}$ is, the larger $R e p_T$ is. Similarly, the bigger ${b_{i}^{'}}^{}$ is, the smaller $R e p_T$ is. The variance of anchor node q denotes the deviating degree of anchor node q's trust value from the expectation value. If the final variance of anchor node q is big, it means the distribution of anchor node q's trust values ( $T r u_T_{q_{1}}, T r u_T_{q_{2}}, \dots, T r u_T_{q_{Q}}$ ) is relatively discrete in Q times network deployment. While the final variance of anchor node q is small, it means that the distribution of anchor node q's trust values is relatively concentrated. The differences between most benign anchor nodes' trust values and their average trust value are larger than those of malicious anchor nodes, that is, $σ_{benign}$ > $σ_{malicious}$ . The weight $σ_{q} / \sum_{q = 1}^{N_{1} + N_{2}} σ_{q}$ of trust values of anchor nodes in formula (12) demonstrates that the trust values of benign anchor nodes account for a higher proportion than malicious anchor nodes' trust values in the judging threshold, which is helpful in excluding malicious anchor nodes. Therefore, formula (12) indicates the most appropriate threshold here.

4.2. The Localization of Sensor Nodes

When utilizing malicious anchor nodes to localize the sensor nodes, the localization accuracy of sensor nodes is very low. To resolve this problem, we eliminate the malicious anchor nodes before the localization phase. The sensor node M utilizes all its multihop communication anchor nodes to estimate its coordinates. The traditional method like maximum likelihood estimation (MLE) has a high computational complexity and always loses much coordinates information.

We employ the weighted Taylor-series least squares algorithm to estimate the coordinates of sensor nodes and the final trust values $T r u_T_{1}$ , $T r u_T_{2}$ , …, $T r u_T_{K}$ ( $q = 1, 2, \dots, K, K \geq 3$ ) of benign anchor nodes are used as the weight in the localization stage. The weighted Taylor-series least squares method can make better use of the anchor information, and the computing accuracy can be greatly improved. The localization processes are as follows.

Assume $d_{m i}$ ( $i = 1, 2, \dots, K$ ) are the measurement distances from the k anchor nodes to the sensor node M and $X_{i} = (x_{i}, y_{i})$ is the declared coordinates of anchor node i. The position of sensor node M is denoted as $X = (x_{0}, y_{0})$ . Therefore, we have a set of the Euclidean equations:

\begin{matrix} T r u_T_{i} \times {∥ X - X_{i} ∥}_{2} = T r u_T_{i} \times d_{m i} . \end{matrix}

(13)

Firstly, calculate the centroid coordinates $X_{C} = (x_{C}, y_{C})$ of K anchor nodes, that is, $X_{C} = (1 / K) \sum_{i = 1}^{K} X_{i}$ .

Secondly, expand the function $f (X) = {∥ X - X_{i} ∥}_{2}$ in Taylor series at $X_{C}$ , and ignore the high-order terms. Equation (13) is transformed into the following modus:

\begin{matrix} T r u_T_{1} (\frac{x_{C} - x_{1}}{d_{1 C}} Δ x + \frac{y_{C} - y_{1}}{d_{1 C}} Δ y) = T r u_T_{1} (d_{1} - d_{1 C}) \\ T r u_T_{2} (\frac{x_{C} - x_{2}}{d_{2 C}} Δ x + \frac{y_{C} - y_{2}}{d_{2 C}} Δ y) = T r u_T_{2} (d_{2} - d_{2 C}) \\ ⋮ \\ T r u_T_{K} ( \frac{x_{C} - x_{K}}{d_{K C}} Δ x + \frac{y_{C} - y_{K}}{d_{K C}} Δ y ) = T r u_T_{K} (d_{K} - d_{K C}), \end{matrix}

(14)

where

d_{i j}

denotes the Euclidean distance between

X_{i}

and

X_{j}

. Therefore,

{Δ X}_{C} = (Δ x_{C}, Δ y_{C})

can be obtained by

Δ X_{C} = {(A^{T} W^{T} W A)}^{- 1} A^{T} W^{T} W B

, where

\begin{matrix} W = [\begin{bmatrix} T r u_T_{1} & 0 & 0 \\ T r u_T_{2} \\ ⋱ & 0 \\ 0 & 0 & T r u_T_{K} \end{bmatrix}], \\ B = [\begin{bmatrix} d_{1} - d_{1 C} \\ d_{2} - d_{2 C} \\ \begin{matrix} ⋮ \end{matrix} \\ d_{K} - d_{K C} \end{bmatrix}], \\ A = {[\begin{bmatrix} \frac{x_{C} - x_{1}}{d_{1 C}} & \frac{x_{C} - x_{2}}{d_{2 C}} & \dots & \frac{x_{C} - x_{K}}{d_{K C}} \\ \frac{y_{C} - y_{1}}{d_{1 C}} & \frac{y_{C} - y_{2}}{d_{2 C}} & \dots & \frac{y_{C} - y_{K}}{d_{K C}} \end{bmatrix}]}^{T} . \end{matrix}

(15)

Thirdly, let $d = \sqrt{Δ x_{C}^{2} + Δ y_{C}^{2}}$ , and judge whether the iteration termination condition $d \leq η$ is satisfied, where η is a prior-defined threshold. If $d \leq η$ , we stop the iteration process. Otherwise, we set $X_{C} = X_{C} + Δ X_{C}$ and go to the second step.

Finally, repeat the second step and the third step until the iteration termination condition is satisfied or the maximum iteration number is reached. The final output $X_{C}$ is the estimated coordinates of sensor node M.

5. Performance Evaluation

In this section, the performance of the BRSL algorithm is tested. All simulations are executed in MATLAB.

The WSN is in a hostile environment, and the malicious anchor nodes are in two conditions: noncolluding or colluding. The default network configuration parameters are shown in Table 1. Unless specified, the default parameters are used in the simulations.

Table 1

Default network configuration parameters.

Parameters	Values
Network size (A)	200 m × 200 m
Deployment strategy	Random
Number of nodes ( $N = N_{1} + N_{2} + N_{3}$ )	200
Number of benign anchor nodes ( $N_{1}$ )	20
Number of malicious anchor nodes ( $N_{2}$ )	10
Number of normal sensor nodes ( $N_{3}$ )	170
Number of simulation rounds (Q)	1000
TTL	4
Trust threshold value ∇	Formula (12)
Communication radius (R)	30 m
$e_{\max}$	0.1R
The standard deviation λ	1
Network connectivity	8~12

Figure 3 shows the random network deployment, and each anchor node has a unique ID in all the simulations, where benign anchor nodes' IDs are from 1 to 20 and malicious anchor nodes' IDs are from 21 to 30.

Figure 3

Network deployment.

5.1. Trust Evaluation of Anchor Nodes

Firstly, we analyze the trust evaluation of anchor nodes. Figures 4 and 5 show that the final variances of benign anchor nodes are bigger than those of the malicious anchor nodes, no matter whether the malicious anchor nodes are noncolluding or colluding. Therefore, the weight $σ_{q} / \sum_{q = 1}^{N_{1} + N_{2}} σ_{q}$ is proper in this paper. When malicious anchor nodes are in noncolluding condition, from Figure 6, we can see that the final trust values of benign anchor nodes are much larger than those of malicious anchor nodes, and the threshold ∇ is about 0.267032. Therefore, we can remove all the malicious anchor nodes before the localization stage. When malicious anchor nodes are colluding, as Figure 7 shows, some of the malicious anchor nodes' final trust values are bigger than those of benign anchor nodes, and the threshold ∇ is about 0.297201. Although all the malicious anchor nodes can be excluded by the threshold, some benign anchor nodes are also removed. But in Section 5.2, it proves that the localization accuracy is still high although some benign anchor nodes are excluded.

Figure 4

Final variances of anchor nodes when malicious anchors are in noncolluding condition.

Figure 5

Final variances of anchor nodes when malicious anchors are in colluding condition.

Figure 6

Final trust values of anchor nodes when malicious anchor nodes are in noncolluding scenario.

Figure 7

Final trust values of anchor nodes when malicious anchors are in colluding scenario.

5.2. Evaluation of BRSL Algorithm

In this subsection, we compare the average localization error (ALE) of the BRSL algorithm with other localization techniques: RMLA2 [15], RMLA1 [15], Bilateration [21], and the traditional multihop localization method without trust evaluation in which Taylor-series least squares solver is used (t-TLS for short). Based on our simulations, we show that BRSL has superior performance in localization accuracy.

The ALE is normalized by the nodes' communication radius R:

\begin{matrix} ALE = \frac{1}{N_{3} R} \sum_{i = N_{1} + N_{2} + 1}^{N} {∥ X_{i} - X_{i}^{'} ∥}_{2}, \end{matrix}

(16)

where

X_{i}

is the estimated coordinates of sensor node i and

X_{i}^{'}

is the real coordinates of sensor node i.

Figures 8 and 9 show the impact of malicious anchor number on the localization accuracy of BRSL, RMLA2, RMLA1, Bilateration, and t-TLS. With the increase of number of malicious anchor nodes, the ALE of RMLA2, RMLA1, Bilateration, and t-TLS rises obviously, while that of BRSL remains stable (no more than 22% in noncolluding scenario and 30% in colluding scenario). Therefore, BRSL is robust for multihop localization and can greatly improve the average localization accuracy no matter the malicious anchor nodes are noncolluding or colluding.

Figure 8

ALE versus malicious anchor number when malicious anchor nodes are noncolluding.

Figure 9

ALE versus malicious anchor number when malicious anchor nodes are colluding.

Figures 10 and 11 show the comparison results of ALE under different standard deviation λ of ranging errors in noncolluding and colluding scenario, respectively. The ALE of each algorithm increases with standard deviation λ. Compared with RMLA2, RMLA1, Bilateration, and t-TLS, BRSL may approximately improve the localization accuracy by 10%, 15%, 55%, and 110%, respectively, in noncolluding scenario and 15%, 20%, 65%, and 150% in colluding scenario. The BRSL performs much better than other algorithms.

Figure 10

ALE versus the standard deviation λ when malicious anchor nodes are in noncolluding scenario.

Figure 11

ALE versus the standard deviation λ when malicious anchor nodes are in colluding scenario.

Figures 12 and 13 illustrate the relationship of ALE with the times of network deployment. The number of simulation rounds equals to the times of network deployment. The ALE almost does not change with the number of simulation rounds whether the malicious anchor nodes are in noncolluding or colluding condition. The variety of network topology does not affect the detecting and localization process.

Figure 12

ALE versus rounds number when malicious anchor nodes are noncolluding.

Figure 13

ALE versus rounds number when malicious anchor nodes are colluding.

5.3. Cost Analysis

Finally, we analyze the costs of five algorithms. Assume a sensor node $M_{j}$ can hear n anchor nodes in its one-hop range. In BRSL method, $M_{j}$ needs to compute $(\begin{smallmatrix} n \\ 2 \end{smallmatrix})$ times to detect each anchor node. Thus, the cost of reputation computation in the network is $O (N_{3} \cdot n^{2})$ . The computation complexity of the localization stage in our method is $O (n)$ . Then the total cost of BRSL method is $O (N_{3} \cdot n^{2}) + O (n)$ . The costs of RMLA2 equals to that of RMLA1. The communication complexity of RMLA1 or RMLA2 is $O (N_{3} \cdot n^{2})$ . And the computation complexity of RMLA1 or RMLA2 is $O (n)$ . Thus, the total cost of RMLA1 or RMLA2 is $O (N_{3} \cdot n^{2}) + O (n)$ , which is the same as BRSL algorithm. The costs of Bilateration and t-TLS mainly focus on the computation stage. The computation complexity of Bilateration is $O (n^{2})$ , while that of t-TLS is $O (n)$ . Therefore, the cost of our method is moderate and acceptable.

6. Conclusions

In this paper, we propose a BRS-based robust secure localization algorithm for the case of presence of malicious anchor nodes. Based on the beta reputation system and the trust evaluation, the malicious anchor nodes are detected and excluded. By utilizing the weighted Taylor-series least squares method, the coordinates of sensor nodes are estimated. The simulation results demonstrate that the BRSL algorithm can effectively distinguish malicious anchor nodes and improve localization accuracy, as well as resist topology variety and ranging uncertainties. In the future, our work will focus on the secure localization when there are multiple and different attacks in complex environments.

Footnotes

Acknowledgments

The authors are grateful to the anonymous reviewers for their industrious work and insightful comments. This work is supported by National Natural Science Foundation of China under Grant nos. 61001138 and 61201317.

References

Albowicz

Chen

Zhang

Recursive position estimation in sensor networks

Proceedings of the 9th International Conference on Network Protocols

2001

35 41

Oliveira

H. A.

Nakamura

E. F.

Loureiro

A. A. F.

Boukerche

Directed position estimation: a recursive localization approach for wireless sensor networks

Proceedings of the 14th IEEE International Conference on Computer Communications and Networks

2005

San Diego, Calif, USA

557 562

Huang

Blum

B. M.

Stankovic

J. A.

Abdelzaher

Range-free localization schemes for large scale sensor networks

Proceedings of the 9th Annual International Conference Mobile Computing and Networking (MobiCom ′03)

2003

San Diego, Calif, USA

ACM Press

81 95

Sichitiu

M. L.

Ramadurai

Localization of wireless sensor networks with a mobile beacon

Proceedings of the 1st IEEE International Conference on Mobile Ad-Hoc and Sensor Systems

October 2004

Fort Lauderdale, Fla, USA

174 183

2-s2.0-20344396105

Guo

X. L.

Feng

R. J.

Y. F.

Wan

J. W.

Grid-Scan-Based multi-hop Localization algorithm for wireless sensor networks

Proceedings of IEEE Sensors Conference

2010

Waikoloa, Hawaii, USA

668 672

Niculescu

Nath

DV based positioning in ad hoc networks

Telecommunication Systems 2003 22 267 280

10.1023/A:1023403323460

Guo

Y. J.

Hedley

TOA-based distributed localisation with unknown internal delays and clock frequency offsets in wireless sensor networks

IET Signal Processing 2009 3 2 106 118

2-s2.0-60449119578

10.1049/iet-spr:20080029

Wan

Feng

Localization refinement for wireless sensor networks

Computer Communications 2009 32 1515 1524

10.1016/j.comcom.2009.05.011

Lim

Hou

J. C.

Localization for anisotropic sensor networks

Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies

2005

138 149

10.

Wan

J. W.

Guo

X. L.

Y. F.

Feng

R. J.

Multi-hop localization algorithm based on grid-scanning for wireless sensor networks

Sensors 2011 11 4 3908 3938

2-s2.0-79953906149

10.3390/s110403908

11.

Shang

Shi

Ahmed

A. A.

Performance study of localization methods for ad-hoc sensor networks

Proceedings of the IEEE International Conference on Mobile Ad-Hoc and Sensor Systems

October 2004

184 193

2-s2.0-20344364148

12.

Wong

S. Y.

Lim

J. G.

Rao

S. V.

Seah

W. K. G.

Multihop localization with density and path length awareness in non-uniform wireless sensor networks

Proceedings of the IEEE 61st Vehicular Technology Conference

June 2005

Stockholm, Sweden

2551 2555

2-s2.0-26444543840

13.

Xiao

Q. J.

Xiao

Cao

J. N.

Wang

J. P.

Multihop range free localization in anisotropic wireless sensor networks: a pattern-driven scheme

IEEE Transactions On Mobile Computing 2010 9 11 1592 1607

14.

Hwang

Kim

Detecting phantom nodes in wireless sensor networks

Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM ′07)

May 2007

2391 2395

2-s2.0-34548329877

10.1109/INFCOM.2007.287

15.

Feng

R. J.

Guo

X. L.

Wan

J. W.

Robust multihop localization for wireless sensor networks with unreliable beacons

International Journal of Distributed Sensor Networks 2012 2012 13

972101

10.1155/2012/972101

16.

Chen

H. L.

Lou

Wang

A novel secure localization approach in wireless sensor networks

Eurasip Journal on Wireless Communications and Networking 2010 2010, article 12

2-s2.0-79251604483

10.1155/2010/981280

17.

Alfaro

J. G.

Barbea

Kranakis

Secure localization of nodes in wireless sensor networks with limited number of truth tellers

Proceedings of the 7th Annual Communication Networks and Services Research Conference (CNSR ′09)

May 2009

86 93

2-s2.0-67650320792

10.1109/CNSR.2009.23

18.

Liu

Ning

Liu

Wang

W. K.

Attack-resistant location estimation in sensor networks

Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN ’05)

2005

4 99 106

19.

Zhu

W. T.

Xiang

Zhou

J. Y.

Deng

R. H.

Bao

Secure localization with attack detection in wireless sensor networks

International Journal of Information Security 2011 10 3 155 171

2-s2.0-79957842998

10.1007/s10207-011-0127-4

20.

Liu

Ning

W. L.

Detecting malicious beacons for secure localization discovery in wireless sensor networks

Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS ′05)

2005

609 619

21.

Hua

Shang

Guo

Yue

L. H.

Bilateration: an attack-resistant localization algorithm of wireless sensor network

Embedded and Ubiquitous Computing 2007 321 332 Lecture Notes in Computer Science

22.

Jsang

Ismail

The beta reputation system

Proceedings of the 15th Bled Electronic Commerce Conference

2002

41 55

23.

Andrews

G. E.

Askey

Roy

R. J.

Special Functions 2001

Cambridge, UK

Cambridge University Press