Sage Journals: Discover world-class research

Abstract

Multihop localization is a popular approach for determining the positions of normal nodes in large-scale wireless sensor networks. However, most existing multihop localization studies assume that the declared positions of beacon nodes are always reliable or even free of errors, which is not a valid assumption in practice. In this paper, we propose a robust multihop localization algorithm (RMLA) based on trust evaluation for diminishing the effect of unreliable beacons on the accuracy of node localization. Firstly, the trust evaluation framework is established on the basis of evidence theory. According to the multihop geometric relationship among nodes, every beacon evaluates the reliability of other beacons' declared positions. Then, the normal nodes integrate the evaluation results to obtain the total trust degrees of their multihop communication beacons, by use of an average method or an enhanced D-S evidence combination rule. Finally, the normal nodes employ the weighted Taylor-series least squares solver to estimate the optimal values of their coordinates. Extensive simulation results in isotropic and anisotropic networks show the robustness and effectiveness of our algorithm.

1. Introduction

Wireless sensor networks (WSNs) which consist of a large number of low-cost, small-size, and multifunctional sensor nodes spark a revolution in the field of information technology (IT). Due to the advantages of easy deployment, self-management, and no requirement for fixed infrastructure, WSNs can be applied to a wide variety of areas, such as environment monitoring, target tracking, traffic management, battlefield spying, healthcare service, and bush fire surveillance [1–6]. In these applications, the sensor nodes need to collaborate with each other in sensing events of interest by exchanging acquired data. To make the data collected from sensor nodes meaningful, the positions of nodes are often required. Being an essential support technology, WSN localization has got more and more attention in recent years [7–12].

WSN localization is to determine the positions of normal nodes based on the knowledge of beacon nodes (beacons for short) and internode distance or bearing measurements. Since the beacons usually obtain their positions through global positioning system (GPS) or manual configuration in fixed places, raising the density of beacons will significantly increase the cost of network deployment. Therefore, the beacons should make up only a small proportion of sensor nodes in large-scale WSNs. In this case, the normal nodes may fail to estimate their positions by directly measuring the distances to beacons due to their short-range measurement abilities. To solve this problem, multihop localization approach is proposed.

In multihop localization, the normal nodes are not necessarily the one-hop neighbors of beacons, and the distances between any pairs of nonneighboring nodes are inferred by approximating the length of the shortest path to the Euclidean distance. A common assumption in most existing multihop localization studies [13–23] is that the beacons' declared positions are always reliable or even free of errors. However, due to several unavoidable factors (e.g., beacon movement, GPS uncertainties, malicious attacks, etc.) in practice, some beacons (called unreliable beacons (UBs)) may broadcast erroneous or inaccurate position information. A representative application scenario is that sensor nodes are deployed in the wild to monitor the bush fire or wildlife behavior. Some fixed beacons may be moved by animals or strong wind because they are normally quite tiny. But they still send their original coordinates that are far away from their current positions. In a typical underwater sensor network [24], the beacons first localize themselves through communicating with the surface buoys, that are equipped with GPS receivers, and then assist normal nodes in estimating their locations. Affected by GPS error, nonline-of-sight (NLOS) and other factors, the beacon positions are subject to certain uncertainties. What is more, in hostile environments, the WSNs may suffer from various kinds of internal or external attacks [25]. Some malicious or compromised beacon nodes may give fake position information to disturb the localization procedure of normal nodes. In the above circumstances, robustness and resistance against UBs is an important concern of WSN localization.

In this paper, we devise a robust multihop localization algorithm (RMLA) based on trust evaluation for solving the node self-localization problem in the presence of UBs. To the best of our knowledge, this paper is the first one that introduces the idea of trust evaluation into the unreliable beacon-tolerant multihop localization. In RMLA algorithm, the beacons first observe each other to evaluate the credibility of their multihop communication beacons. Specially, the concepts of evidence theory are employed to deal with the uncertainty factors in trust evaluation. Then the normal nodes integrate the evaluation results to obtain a total view about the trust degrees of their multihop communication beacons. Finally, the normal nodes use the total trust degrees of beacons as weights to achieve robust estimation of their positions. As all these above operations are carried out on each sensor node, RMLA is a completely distributed localization approach with less communication and computation cost. Through simulations, we demonstrate that RMLA can efficiently reduce the influence of both UBs and distance estimation errors on node multihop localization. Under various conditions, compared with some existing localization algorithms, RMLA has apparent advantages in accuracy and robustness.

The rest of this paper is organized as follows. In Section 2 we introduce related works on multihop localization and unreliable beacon-tolerant localization. In Section 3 we formulate the multihop localization problem and introduce some necessary definitions. In Section 4 we present the details of our proposed RMLA algorithm. Section 5 evaluates the performance of RMLA algorithm through simulations. Lastly, Section 6 concludes this paper.

2. Related Works

2.1. Multihop Localization Studies

Based on the idea of distance vector (DV) routing and GPS positioning, Niculescu and Nath [13] proposed two low-cost localization solutions, called DV-distance (range-based) and DV-hop (range-free) algorithms. They are the origination of multihop localization schemes for WSNs. In both algorithms, the lengths of shortest paths or minimum hop counts to beacons are estimated through the message flooding that is similar to the distance vector routing. The accuracy of DV-distance and DV-hop is built on the assumption that the shortest path between a pair of nodes is close to a straight line, which may not always be achievable in anisotropic networks. Shang et al. [14] studied the effect of beacon selection on multihop localization of WSNs. The experimental results show that using only the four nearest beacons could get better localization performance in most cases. In this paper, we denote this method as 4-Multihop. Lim and Hou [15] designed a proximity-distance map (PDM) to characterize the anisotropic features of WSNs. Firstly, the beacons derive an optimal linear transformation collaboratively to map the precise Euclidean distances and the proximities between pairwise beacons. Then, the map is sent to normal nodes to assist them in modifying their multihop estimative distances. The intuition of PDM is that the topology character of entire WSN can be well represented by beacons, but it is not the case in beacon-clustered networks. Cheng et al. [16] developed an algorithm called hybrid localization (HyBloc) to provide reliable localization service with a limited number of clustered beacons. It combines two techniques: MDS-MAP and PDM. HyBloc is less susceptible to the adverse effect of beacon placement, but it requires more communication and computation cost than PDM. Wong et al. [17] proposed a density-aware hop-count localization (DHL) algorithm. In DHL, node density is considered, and an empirical range ratio (the ratio of expected hop distance to node's communication range for a given local density) table is constructed to reduce the overestimation of multihop distances. Wang and Xiao [18] presented an improved multihop algorithm called i-Multihop to minimize the effect of erroneous multihop estimative distances on node localization. First, the upper bound constraints are utilized to filter out the incorrect distance estimations, and the estimated positions of nodes are pinpointed to the intersection constrained by the correct distances. Second, the distance fitting is used to fit the correct distance measurements, which makes the final estimated positions less affected by the layout of beacons. But i-Multihop has higher computation complexity. Severi et al. [19] gave a constrained semidefinite programming localization algorithm (CSDPLA) which is highly robust when inaccurate range information is present. CSDPLA can run in both centralized and distributed ways and reduce communication cost compared with the classic message-passing localization solutions. To tolerate network anisotropy, Xiao et al. [20] introduced a distributed pattern-driven scheme to produce accurate multihop distance estimation. The main idea of the pattern-driven scheme is to exploit the observation that in anisotropic networks the hop count field propagated from a beacon exhibits three patterns, namely, concentric ring (CR), centrifugal gradient (CG), and distorted gradient (DG). For each pattern has its dominating error source in multihop distances, different distance estimation schemes are adopted in node localization. Lee and Kim [21] considered the relationship between node's communication range and localization accuracy of range-free schemes and proposed a selection method of communication range for DV-Hop algorithm. By utilizing the selection method, DV-Hop can produce more accurate estimations of average hop distances for normal nodes, and therefore obtain better localization results than the algorithms with fixed communication range. Guo et al. [22] designed a backpropagation (BP) neural network-based localization algorithm (BPL) for three-dimensional (3D) WSNs, in which a BP model is constructed to revise the multihop estimative distances among non-neighboring nodes. Actually BPL is a semidistributed localization solution. Wan et al. [23] gave a light-weight multihop localization algorithm based on grid-scanning (MLGS). By computing the intersection of bounding square rings, the candidates of node coordinates are restricted within a small scope. Then, the close-to-optimal values of node coordinates are searched through a grid-scanning procedure. When all beacons are reliable, MLGS has better adaptability to irregular network topology and lower computation complexity for node localization in large-scale WSNs.

2.2. Unreliable Beacon-Tolerant Localization Studies

In the literature, Kuo et al. [26] defined the beacon movement detection (BMD) problem and proposed four BMD schemes to reduce the effect of beacon movement on node localization. Through mutual observations among beacons, the BMD engine automatically monitors the unnoticed location changes of beacons. After identifying such UBs, the WSNs remove them from the localization engine. Fan et al. [27] presented a two-step localization algorithm to deal with the case, where both inaccurately positioned beacons and ranging error accumulation exist. First, a ranging error-tolerable topology reconstruction method is utilized to estimate the relative positions of sensor nodes. Then, the inaccurately positioned beacons are detected according to the pairs of connected beacons. Both steps need to be performed in a central controller. Based on the fusion of GPS measurements and beacon-to-beacon distance or angle-of-arrival (AOA) estimates, Yu and Guo [28] devised an effective approach to improve the accuracy of beacon positions for both line-of-sight (LOS) and NLOS scenarios. But this method is only suitable to the beacons equipped with GPS receivers. Srirangarajan et al. [29] developed a distributed localization algorithm based on second-order cone programming (SOCP) relaxation. In the presence of beacon position errors, the beacons refine their positions by using the relative distance information communicated with their neighbors. Due to frequent information exchange, this algorithm is energy-inefficient. Vemula et al. [30] formulated node localization from a probabilistic point of view. They proposed four iterative and Monte Carlo sampling-based methods that incorporate beacon position uncertainties to estimate the position distribution (mean and covariance) of normal nodes. These methods have relatively good performance in inhibiting the accumulation of localization errors. Lui et al. [31] brought forward a novel semi-definite programming algorithm for WSN localization with uncertainties in both beacon position and signal propagation speed and presented its simplified form assuming that beacon position errors are independently and identically distributed. Srinivasan et al. [32] introduced the concept of reputation to WSN localization and proposed an approach called distributed reputation-based beacon trust system (DRBTS) for excluding malicious beacons that provide false location information. In DRBTS, each beacon monitors its one-hop neighborhood for misbehaving beacons and updates the reputations of the corresponding beacons. When estimating their coordinates, the normal nodes adopt a simple majority voting scheme to determine whether or not to use a given beacon's location information. Park and Shin [33] gave an attack-tolerant localization protocol, named verification for iterative localization (VeIL). By exploiting the high spatiotemporal correlation existing among neighboring nodes, VeIL can prevent most of the UBs from localization system. Zhu et al. [34] proposed an innovative modular solution featuring two light-weight-modules that are for dedicated functionalities, respectively, but can also be closely integrated. First, some simple geometric triangular rules and an efficient voting technique are harnessed to enable the attack detection module which identifies and filters out unreliable location references. Then, a secure localization module is constructed to compute and cluster certain reference points and estimate the position of normal node with the centroid of the most valuable reference points identified. Jadliwala et al. [35] theoretically analyzed the necessary and sufficient conditions to guarantee a bounded localization error during a two-dimensional (2D) distance-based location estimation in the presence of UBs. On this basis, they outlined three distance-based localization algorithms that can guarantee the localization accuracy, when UB number is below a given threshold. These studies above mainly concentrate on the one-hop or centralized WSN localization. Most of them require densely deployed beacons and higher communication cost, which limit their widespread application in large-scale WSNs.

3. Preliminaries

3.1. Problem Formulation

We consider a network consisting of P beacon nodes and Q normal nodes. All nodes are randomly distributed in a 3D spatial region. The identities (IDs) of beacon nodes are from 1 to P, and those of normal nodes are from $P + 1$ to $P + Q$ . Every node is capable of measuring the distance to any of its immediate neighbors. The ranging error ε follows the zero-mean Gaussian distribution, that is, $ε ~ N (0, λ^{2})$ , where λ is the standard deviation of ranging errors. Every node's communication and ranging radius is R. In multihop localization, each beacon first 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. Through hop-by-hop dissemination of the estimated distances to beacons, every node could estimate the lengths of shortest paths (i.e., multihop estimative distances) to beacons.

As shown in Figure 1, when the normal node $N_{u}$ gets enough estimated distances $d_{u i}$ to beacons $N_{i}$ ( $i = 1, 2, \dots, K$ ), $K \geq 4$ , a system of Euclidean equations can be set up:

\begin{gathered} \sqrt{{(x_{u} - x_{1})}^{2} + {(y_{u} - y_{1})}^{2} + {(z_{u} - z_{1})}^{2}} = d_{u 1}, \\ \sqrt{{(x_{u} - x_{2})}^{2} + {(y_{u} - y_{2})}^{2} + {(z_{u} - z_{2})}^{2}} = d_{u 2}, \\ ⋮ \\ \sqrt{{(x_{u} - x_{K})}^{2} + {(y_{u} - y_{K})}^{2} + {(z_{u} - z_{K})}^{2}} = d_{u K}, \end{gathered}

(1)

where

X_{u}

{[x_{u}, y_{u}, z_{u}]}^{T}

N_{u}

's coordinates that need to be estimated,

X_{i}

{[x_{i}, y_{i}, z_{i}]}^{T}

is beacon

N_{i}

's declared position.

Figure 1

Node localization with an unreliable beacon.

Generally, $X_{u}$ should be located in the intersection of K spheres of which the centers and radiuses are $X_{i}$ and $d_{u i}$ , respectively. The smaller the intersection is, the more accurately $X_{u}$ can be pinpointed. When both $X_{i}$ and $d_{u i}$ are accurate, the $X_{u}$ can be well estimated by solving (1). However, if an UB exists (e.g., $N_{2}$ is a malicious beacon, its declared position is far from its real location), the system would incorrectly estimate the $X_{u}$ to a location that is close to the UB's declared position. It will be even worse and complex, when more beacons are unreliable. In practice, the UBs may seriously affect the localization accuracy of normal nodes and further endanger the applications of WSNs. How to mitigate the influence of UBs and improve the accuracy and robustness of WSN multihop localization is the main topic of our study.

3.2. Related Definitions

Before describing our proposed algorithm, we first introduce some necessary definitions: (1)

multihop communication range: the largest range that a node's propagation packet can reach through multihop forwarding. In dense networks, the radius of a node's multihop communication range is approximately TTL (time to live, i.e., the maximum times that a node's propagation packet can be forwarded) times of its communication radius R;

(2)

multihop communication beacon: If a node $N_{p}$ can communicate with a beacon $N_{i}$ in one-hop or multihop manner, that is, the beacon $N_{i}$ is in the TTL field of $N_{p}$ 's propagation packet, the beacon $N_{i}$ is called $N_{p}$ 's multihop communication beacon. The set of $N_{p}$ 's all multihop communication beacons is denoted by $C_{p}$ ;

(3)

multihop count: the number of line segments in the shortest path between a pair of sensor nodes. If the shortest path $V_{p q}$ between nodes $N_{p}$ and $N_{q}$ passes L nodes (including $N_{p}$ and $N_{q}$ ), $V_{p q}$ 's multihop count is $H_{p q} = L - 1$ ;

(4)

calculated distance: the Euclidean distance between the declared positions of pairwise beacons. If the declared coordinates of beacons $N_{i}$ and $N_{j}$ are respectively $X_{i}$ and $X_{j}$ , the calculated distance between $N_{i}$ and $N_{j}$ is denoted by,

D_{i j} = {‖ X_{i} - X_{j} ‖}_{2} = \sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2} + {(z_{i} - z_{j})}^{2}} .

(2)

4. Robust Multihop Localization Algorithm

In RMLA algorithm, each beacon evaluates the reliability of other beacons according to the multihop geometric relationship among them, which helps the normal nodes obtain the total trust degrees of their multihop communication beacons and further lays a foundation for robust localization of WSNs. In general, the RMLA algorithm includes three main phases: trust evaluation among beacons, calculation of integrated trust values and weighted estimation of node coordinates. The details of RMLA algorithm are given in the following.

4.1. Trust Evaluation Framework

Trust is an evaluation behavior of a subject to an object. It specifies, evaluates, and sets up trust relationship among entities. Due to the subjectivity of trust evaluation, the evaluation results usually suffer from certain uncertainties. In order to bring the uncertainty factor into the trust evaluation among nodes and make it more reasonable, we employ the concepts of evidence theory [36] to construct the trust evaluation framework in RMLA.

Firstly, we define the identification frame $Θ = [T, U]$ , where T and U represent two exclusive trust states of beacons, namely, “trust” and “distrust.” The power set of $Θ$ is $2^{Θ} = {Ø, {T}, {T, U}, {U}}$ , in which Ø represents the empty set (impossible event), and ${T, U}$ represents the “uncertainty” trust state. Then, we construct the basic probability assignment (BPA) function $m : 2^{Θ} \to [0, 1]$ , in which the BPA values $m (T)$ , $m (T, U)$ , and $m (U)$ represent the basic confidence level of the following propositions: the beacon is credible, the beacon's trust state is uncertain, and the beacon is incredible. Thus, we can transfer the proposition inference into the set calculation. In this paper, the trust degree $B_{i}$ of beacon $N_{i}$ is defined as the total reliability of proposition T:

B_{i} = Bel (T) = \sum_{X \subseteq T} m (X) = m (T) .

(3)

In evidence theory, as the rationality and objectivity of BPA function directly influence the accuracy and effectiveness of the evidence fusion, how to determine the BPA function is a key issue. Overall, the BPA values of trust evaluation among beacons should follow the two basic principles: (1)

the sum of all BPA values is equal to 1, that is, $m (T) + m (T, U) + m (U) = 1$ . This is derived from the definition of BPA function;

(2)

the BPA values are dependent on the multihop geometric relationship among beacons. In general, the smaller the difference between the multihop estimative distance (approximation of the Euclidean distance) and the calculated distance is, the larger $m (T)$ is, and the smaller $m (T, U)$ and $m (U)$ are. Otherwise, the smaller $m (T)$ is, and the larger $m (T, U)$ and $m (U)$ are.

4.2. Trust Evaluation among Beacons

Figure 2 shows the multihop geometric relationship among beacons, in which $N_{i}$ ; $N_{j}$ represent beacon nodes, and $N_{a}$ ; $N_{b}$ represent normal nodes. We first consider the ideal condition, where the declared positions of beacons are accurate. According to the declared coordinates of $N_{j}$ , the beacon $N_{i}$ can compute the calculated distance to $N_{j}$ , denoted by $D_{i j}$ . The multihop estimative distance and multihop count between $N_{i}$ and $N_{j}$ are $d_{i j} = d_{i a} + d_{a b} + d_{b j}$ and $H_{i j} = 3$ , respectively. For $N_{i}$ and $N_{j}$ are not adjacent (i.e., $N_{j}$ is out of $N_{i}$ 's one-hop communication range), the Euclidean distance (equal to the calculated distance under the ideal condition) between them is bigger than their communication radius R, that is, $D_{i j} > R$ . According to ( $d_{i a}$ , $d_{a b}$ , $d_{b j}$ ) ≤ R, we can infer that $d_{i j} \leq 3 R$ . Based on the idea of beeline distance, we can further infer that $D_{i j}$ ≤ $d_{i j}$ . Therefore, the ideal multihop geometric relationship between $N_{i}$ and $N_{j}$ should satisfy $R < D_{i j} \leq d_{i j} \leq H_{i j} R$ .

Figure 2

Multihop geometric relationship among beacons.

We then extend our consideration to the general case, where the declared positions of beacons may be unreliable. Taking R and $H_{i j} R$ as the boundary points, we divide the trust evaluation of $N_{i}$ to $N_{j}$ (i.e., how $N_{i}$ determine the trust evaluation values $M_{i j} = {m_{i j} (T), m_{i j} (T, U), m_{i j} (U)}$ of $N_{j}$ 's declared coordinates $X_{j}$ ) into the following three cases. (1)

if the calculated distance between $N_{i}$ and $N_{j}$ exceeds $H_{i j}$ times of nodes' communication radius, that is, $D_{i j} > H_{i j} R$ , $N_{i}$ should consider that the declared position of $N_{j}$ is incredible. Then $N_{i}$ should set the trust evaluation values $M_{i j}$ as follows:

\begin{gathered} m_{i j} (T) = 0, \\ m_{i j} (T, U) = τ_{1}, \\ m_{i j} (U) = 1 - τ_{1} . \end{gathered}

(4)

In practice, due to the influence of environment noise, the measurable distances among neighboring nodes are not exactly accurate. This may lead to the case that a few measurements among neighboring beacons are a little bigger than R (or a few multihop estimative distances between pairwise nonadjacent beacons slightly exceed $H_{i j} R$ ). In order to prevent the event that beacon $N_{i}$ incorrectly considers the reliable beacon $N_{j}$ completely unreliable from appearance in this occasional case, the BPA value $m_{i j} (T, U)$ of “uncertainty” in (4) is set to a very small positive decimal $τ_{1}$ (such as 0.01). The value of $τ_{1}$ mainly depends on the ranging abilities of sensor nodes. If sensor nodes have higher ranging accuracy (i.e., λ is smaller, where λ is the standard deviation of ranging errors), $τ_{1}$ should be set to a smaller value. Otherwise, a bigger value should be given to $τ_{1}$ .

(2)

If the calculated distance $D_{i j} \leq H_{i j} R$ , but the difference between $D_{i j}$ and the multihop estimative distance $d_{i j}$ is larger than nodes' communication radius R (i.e., $| D_{i j} - d_{i j} | > R$ ), $N_{i}$ should still consider that the credibility of $N_{j}$ 's declared position is not very high. In this case, we have

\begin{gathered} m_{i j} (T) = 1 - τ_{2} - ω_{2}, \\ m_{i j} (T, U) = τ_{2}, \\ m_{i j} (U) = ω_{2}, \end{gathered}

(5)

where $τ_{2}$ and $ω_{2}$ are positive decimals between 0 and 1. Their values should be determined based on multihop count $H_{i j}$ , local network topology and some other factors. Concretely speaking, $τ_{2}$ should be proportional to multihop count $H_{i j}$ (i.e., $τ_{2} \propto H_{i j}$ ) and be in inverse proportion to $N_{i}$ 's local density $I_{i}$ (an important parameter that reflects the feature of local network topology) (i.e., $τ_{2} \propto 1 / I_{i}$ ). This is because larger multihop count and lower local density would make multihop estimative distances far away from Euclidean distances, which raises the uncertainty of trust evaluation. In contrast to $τ_{2}$ , $ω_{2}$ should be in inverse proportion to $H_{i j}$ (i.e., $ω_{2} \propto 1 / H_{i j}$ ) and be proportional to $I_{i}$ (i.e., $ω_{2} \propto I_{i}$ ). In general, $τ_{2}$ is close to 0 (such as 0.1) and $ω_{2}$ is close to 1 (such as 0.8).

(3)

If $D_{i j} \leq H_{i j} R$ , and the difference between $D_{i j}$ and $d_{i j}$ is no more than R (i.e., $| D_{i j} - d_{i j} | \leq R$ ), the trust evaluation value $M_{i j}$ of $N_{i}$ to $N_{j}$ should be ascertained according to the difference $ε_{i j}$ between $D_{i j}$ and $d_{i j}$ . Thus,

\begin{gathered} m_{i j} (T) = 1 - \frac{ε_{i j}}{R} = 1 - \frac{| D_{i j} - d_{i j} |}{R}, \\ m_{i j} (T, U) = 1 - m_{i j} (T), \\ m_{i j} (U) = 0 . \end{gathered}

(6)

In multihop scenario, most of trust evaluations among beacons belong to this case. For large-scale or sparse WSNs, we can set a smaller TTL value to reduce the impact of detoured paths on multihop distance estimation. Then the trust evaluation is only confined to the local range (i.e., node's multihop communication range) of WSNs, which prevents the appearance of bigger $ε_{i j}$ between pairwise reliable beacons. In (6), we simplify the mapping between $m_{i j} (T)$ and $ε_{i j}$ to a linear relationship. Actually, their mapping relationship is more complex. If we need to further improve the accuracy of trust evaluation, the determination of $m_{i j} (T)$ should also be combined with the specific network parameters, such as node's ranging ability, multihop count, node's local density, and so forth. For instance, $m_{i j} (T)$ may be in inverse proportion to λ and $H_{i j}$ (i.e., $m_{i j} (T) \propto 1 / λ$ , $m_{i j} (T) \propto 1 / H_{i j}$ ), and be proportional to $I_{i}$ (i.e., $m_{i j} (T) \propto I_{i}$ ). Thus, an accurate expression of $m_{i j} (T)$ can be written as $m_{i j} (T) = f (ε_{i j}, λ, H_{i j}, I_{i})$ . In order to simplify the computation complexity of trust evaluation, this paper employs the simple linearity in (6) by default.

4.3. Calculation of Integrated Trust Values

After the beacon $N_{i}$ obtains the trust evaluation values $M_{i} = {M_{i j} | N_{j} \in C_{i}}$ of its all multihop communication beacons ( $C_{i}$ ), it broadcasts $M_{i}$ to the network in a multihop flooding manner. The normal nodes store the trust evaluation values they received, based on which they could calculate the integrated trust values of their multihop communication beacons. Additionally, during this phase, every beacon or normal node could optionally update its trust evaluation results according to other nodes' broadcast information.

Figure 3 shows how the normal node $N_{u}$ integrates the trust evaluation values of its multihop communication beacon $N_{k}$ . The circles represent nodes' multihop communication ranges. In the phase of trust evaluation among beacons, all beacons ( $C_{k}$ ) in $N_{k}$ 's multihop communication range evaluate the credibility of $N_{k}$ 's declared position. Through the multihop propagation of beacons' evaluation results, the normal node $N_{u}$ can receive the trust evaluation values of $N_{k}$ from some of its multihop communication beacons ( $C_{u}$ ). When $N_{u}$ receives J trust evaluation values $M_{j k} (j = 1, 2, \dots, J)$ of $N_{k}$ from beacons $N_{j} (N_{j} \in C_{u} \cap C_{k})$ , $N_{u}$ could combine all $M_{j k}$ to obtain an integrated trust value $Z_{u k} = {m_{u k} (T), m_{u k} (T, U), m_{u k} (U)}$ of $N_{k}$ . In this paper, we give two combination methods for calculating the integrated trust values of beacons. (1)

average method: assuming the weights of trust evaluation values $M_{j k} (j = 1, 2, \dots, J)$ obtained from the beacons $N_{j} \in C_{u} \cap C_{k}$ are equivalent. From the perspective of traditional probability theory, we take the average value of all $M_{j k}$ as the integrated trust value $Z_{u k}$ of the normal node $N_{u}$ to the beacon $N_{k}$ :

\begin{matrix} Z_{u k} & = \frac{1}{J} \sum_{j = 1}^{J} M_{j k} \\ = {\frac{1}{J} \sum_{j = 1}^{J} m_{j k} (T), \frac{1}{J} \sum_{j = 1}^{J} m_{j k} (T, U), \frac{1}{J} \sum_{j = 1}^{J} m_{j k} (U)} . \end{matrix}

(7)

This average method is simple and requires less computation cost. But it only balances the beacons' viewpoints, while does not make full use of the uncertainty information in trust evaluation values. Its integration performance needs to be further improved.

(2)

enhanced D-S combination method: in evidence theory, the Dempster-Shafer (abbreviated D-S) combination method [36] is a basic rule to evaluate the joint effect of evidences. It can integrate the fuzzy and uncertain information arising from multiple aspects. If the conflict among evidences is weak, the D-S method has preferable integration performance. However, in the trust evaluation among beacons, some beacons (especially the UBs) may produce evaluation results that are far from most beacons' viewpoints. In this case, there would be strong conflict among evidences, which results in the reduction of combination performance of D-S method. In order to diminish the influence of evidence conflict on trust value integration, we adopt the enhanced D-S combination method in the following.

Figure 3

Integration of trust evaluation values.

Firstly, we define the deviation degree of evidence:

δ_{j k} = {‖ M_{j k} - \frac{1}{J} \sum_{j = 1}^{J} M_{j k} ‖}_{2} .

(8)

When δ _jk is large, that is, $M_{j k}$ is far from the average viewpoint of J beacons, we consider that there is strong conflict between $M_{j k}$ and other evidences. Otherwise, $M_{j k}$ was relatively consistent with other evidences. We set a threshold Δ to judge whether $M_{j k}$ should be accepted to participate in the evidence combination:

{\begin{cases} δ_{j k} \leq Δ, M_{j k} is accepted, \\ δ_{j k} > Δ, M_{j k} is refused . \end{cases}

(9)

Here, we briefly discuss how to set the value of threshold Δ. As $δ_{j k}$ is essentially the distance of two trust evaluation values, its maximum is $\sqrt{2}$ . In order to make (9) meaningful, Δ should be no more than 1.414 (i.e., Δ ≤ 1.414). In general, Δ is mainly affected by the UB number. When there are more UBs in WSNs, we should set Δ a smaller value to refuse conflicting evidences as many as possible. In contrast, if the UB number is smaller, Δ should be set to a bigger value. In our experience, when 0.6 ≤ Δ ≤ 1.1, the majority of conflicting evidences caused by UBs can be filtered out.

According to (9), the normal node $N_{u}$ could select an evidence set ${M_{1 k}, M_{2 k}, \dots, M_{S k}}$ with smaller conflict, where $S \leq J$ . Then, the integrated trust value $Z_{u k}$ of the beacon $N_{k}$ is calculated by using the traditional D-S combination method:

\begin{matrix} m_{u k} (\emptyset) = 0, \\ m_{u k} (A) = (m_{1 k} \oplus m_{2 k} \oplus \dots \oplus m_{S k}) (A) \\ = \frac{1}{1 - G} \\ \times \sum_{⋂_{j = 1}^{S} A_{j k} = A}^{} m_{1 k} (A_{1 k})  \times  m_{2 k} (A_{2 k})  \times  \dots  \times  m_{S k} (A_{S k}), \\ {A \neq \emptyset, A \subseteq Θ, (A_{1 k}, A_{2 k}, \dots, A_{S k}) \subseteq Θ}, \end{matrix}

(10)

where

G = \sum_{⋂_{j = 1}^{S} A_{j k} = \emptyset}^{} m_{1 k} (A_{1 k}) \times m_{2 k} (A_{2 k}) \times \dots \times m_{S k} (A_{S k}) < 1

Finally, the normal node $N_{u}$ gets the total trust degree $B_{u k} = m_{u k} (T)$ of the beacon $N_{k}$ . Generally, through trust evaluation among nodes, the reliable beacons could be endowed with higher total trust degrees, while the UBs are given lower ones. For both average and enhanced D-S combination methods, we can also set a threshold ξ and compare $B_{u k}$ with ξ. If $B_{u k} \geq ξ$ , $B_{u k}$ is set to 1, otherwise it is set to 0. In practice, this is an optional operation.

4.4. Weighted Estimation of Node Coordinates

In Section 3.1, the essence of solving (1) is to find an optimal $X_{u}$ to minimum the sum of squares of differences between Euclidean distances and multihop estimative distances (EM differences for short), that is, least squares estimation. When an UB exists, its erroneous position information would raise the corresponding EM difference and disturb the least squares estimation. To resolve this problem, two schemes can be used, eliminating the unreliable equation and reducing the weight of the unreliable equation on node coordinate estimation. Considering the former scheme may inevitably lead to a certain loss of valid information, we adopt the latter one. Through multiplying a smaller weight on both sides of the unreliable equation, we can reduce its EM difference in least squares estimation, and therefore diminish the effect of this equation on coordinate estimation.

After the normal node $N_{u}$ gets the total trust degrees $B_{u i} (i = 1, 2, \dots, K)$ of its all multihop communication beacons, we add different weights to the equations in (1) according to $B_{u i}$ :

\begin{gathered} B_{u 1} \sqrt{{(x_{u} - x_{1})}^{2} + {(y_{u} - y_{1})}^{2} + {(z_{u} - z_{1})}^{2}} = B_{u 1} d_{u 1}, \\ B_{u 2} \sqrt{{(x_{u} - x_{2})}^{2} + {(y_{u} - y_{2})}^{2} + {(z_{u} - z_{2})}^{2}} = B_{u 2} d_{u 2}, \\ ⋮ \\ B_{u K} \sqrt{{(x_{u} - x_{K})}^{2} + {(y_{u} - y_{K})}^{2} + {(z_{u} - z_{K})}^{2}} = B_{u K} d_{u K} . \end{gathered}

(11)

By weighting, the beacons with lower trust degrees (or UBs) will have smaller influence on the coordinate estimation of node $N_{u}$ . Then we utilize the weighted Taylor-series least squares solver [37, 38] to calculate the position coordinates of $N_{u}$ : (1)

calculate the centroid coordinates $X_{0} = {[x_{0}, y_{0}, z_{0}]}^{T}$ of K beacons, that is, $X_{0} = 1 / K \sum_{i = 1}^{K} X_{i}$ ;

(2)

expand the function $f (X_{u}) = \sqrt{{(x_{u} - x_{i})}^{2} + {(y_{u} - y_{i})}^{2} + {(z_{u} - z_{i})}^{2}}$ in Taylor series at $X_{0}$ and ignore the high order terms. Equation (11) is transformed into the following form:

\begin{matrix} B_{u 1} (\frac{x_{0} - x_{1}}{r_{1}} Δ x_{u} + \frac{y_{0} - y_{1}}{r_{1}} Δ y_{u} + \frac{z_{0} - z_{1}}{r_{1}} Δ z_{u}) \\ = B_{u 1} (d_{u 1} - r_{1}), \\ B_{u 2} (\frac{x_{0} - x_{2}}{r_{2}} Δ x_{u} + \frac{y_{0} - y_{2}}{r_{2}} Δ y_{u} + \frac{z_{0} - z_{2}}{r_{2}} Δ z_{u}) \\ = B_{u 2} (d_{u 2} - r_{2}), \\ ⋮ \\ B_{u K} (\frac{x_{0} - x_{K}}{r_{K}} Δ x_{u} + \frac{y_{0} - y_{K}}{r_{K}} Δ y_{u} + \frac{z_{0} - z_{K}}{r_{K}} Δ z_{u}) \\ = B_{u K} (d_{u K} - r_{K}), \end{matrix}

(12)

where

r_{i} = {∥ X_{0} - X_{i} ∥}_{2}

represents the Euclidean distance between

X_{0}

and

X_{i}

;

(3)

set

\begin{gathered} W = [\begin{bmatrix} B_{u 1} & 0 & 0 \\ 0 & B_{u 2} & 0 \\ ⋱ \\ 0 & 0 & B_{u K} \end{bmatrix}], \\ A = [\begin{bmatrix} \frac{x_{0} - x_{1}}{r_{1}} & \frac{y_{0} - y_{1}}{r_{1}} & \frac{z_{0} - z_{1}}{r_{1}} \\ \frac{x_{0} - x_{2}}{r_{2}} & \frac{y_{0} - y_{2}}{r_{2}} & \frac{z_{0} - z_{2}}{r_{2}} \\ ⋮ \\ \frac{x_{0} - x_{K}}{r_{K}} & \frac{y_{0} - y_{K}}{r_{K}} & \frac{z_{0} - z_{K}}{r_{K}} \end{bmatrix}], \\ Δ X_{u} = [\begin{bmatrix} Δ x_{u} \\ Δ y_{u} \\ Δ z_{u} \end{bmatrix}], \\ B = [\begin{bmatrix} d_{u 1} - r_{1} \\ d_{u 2} - r_{2} \\ ⋮ \\ d_{u K} - r_{K} \end{bmatrix}], \end{gathered}

(13)

thus (12) can be reformulated as

W A Δ X_{u} = W B;

(14)

(4)

solve (14) by using the least squares method, and we get $Δ X_{u} = {(A^{T} W^{T} W A)}^{- 1} A^{T} W^{T} W B$ ;

(5)

judge whether the iteration termination condition ${∥ Δ X_{u} ∥}_{2} \leq γ$ is satisfied, where γ is a prior-defined and flexible threshold based on the accuracy requirement. If ${∥ Δ X_{u} ∥}_{2} \leq γ$ is satisfied, we stop the iteration process. Otherwise, we set $X_{0} = X_{0} + Δ X_{u}$ and go to step (2);

(6)

repeat steps (2) to (5) until the iteration termination condition is satisfied or the maximum iteration number is reached, whichever comes earlier. The final output $X_{0}$ is the estimated coordinates of $N_{u}$ .

4.5. Discussion of RMLA Algorithm

As all the localization procedures in RMLA are carried out on every sensor node, RMLA is essentially a distributed multihop localization algorithm. Relative to centralized algorithms, RMLA has the advantages that distributed algorithms possess, such as low computation complexity, less communication cost, and high network scalability. As mentioned above, RMLA is comprised of three steps, namely, trust evaluation, trust value integration, and position estimation. Their computation complexities are $O (P)$ , $O (Q)$ , and $O (Q)$ , respectively, where P is the number of beacons, and Q is the number of normal nodes. For large-scale networks, P is usually much smaller than Q. Thus the total computation complexity of RMLA is $O (Q)$ , while that of MDS-MAP (a typical centralized algorithm proposed by Shang et al. [12], in which the matrix comprised by the multihop estimative distances between all pairs of nodes are required) is $O ({(P + Q)}^{3})$ . In localization, RMLA requires only the local information to be sent to the corresponding nodes, while the centralized algorithms need to collect all internode measurements to a central processor. Therefore, RMLA is more energy-efficient than centralized algorithms, especially in large-size WSNs. The detailed discussion about the performance comparison of centralized and distributed algorithms can be found in [8].

For normal nodes, the computation and communication cost required in RMLA is comparable to most existing multihop localization solutions. The additional cost is in the phase of trust value integration in which the normal nodes need to receive the trust evaluation values from beacons (resulting in communication cost) and compute the integrated trust values of their multihop communication beacons (resulting in computation cost). However, relative to the entire process of multihop localization, the cost of trust value integration is lower. It is nearly equivalent to (or even smaller than) the cost required for distance modification in some improved multihop localization solutions, such as PDM [15], Hybloc [16], and BPL [22]. As described in Section 4.4, the weighted calculation of node coordinates includes iteration operations, and the computation cost of normal nodes is related to the iteration number. If requesting higher localization accuracy, we should set the threshold γ a smaller value, which will increase the iteration number and further raise the computation cost. Otherwise, we can set γ a bigger value. Empirically, we could get a better tradeoff between computation cost and localization accuracy of RMLA when $γ = (0.001 ~ 1)$ .

5. Performance Evaluation

In this section, we conduct extensive simulations to study the performance of the proposed RMLA algorithm. All simulations are run in MatLab. Figure 4 shows a typical realization of 3D WSN with a number of UBs. The solid pentagrams “”, hollow pentagrams “”, and solid dots “●” represent reliable beacons, unreliable beacons, and normal nodes, respectively. The default network configuration parameters are shown in Table 1. Unless specified, we use the default parameters in simulations.

Table 1

Default network configuration parameters.

Parameters	Values
Network size (in meters)	200 × 200 × 200
Deployment strategy	Random
Number of nodes ( $P + Q$ )	200
Number of beacon nodes (P)	30
UB Number	8
TTL	5
Ranging radius R (in meters)	$50 ~ 70$
Network connectivity	15
Standard deviation of ranging errors (λ)	1

Figure 4

Network topology (isotropic network).

We first compare the average localization errors (ALEs) of the traditional multihop localization method without trust evaluation (abbrevd. t-Multihop) in which Taylor-series least squares solver is also used to compute nodes' coordinates, the proposed algorithm with average method (abbrevd. RMLA1) and the proposed algorithm with enhanced D-S combination rule (abbrevd. RMLA2). Then, we present the accuracy comparison results of our RMLA methods and other typical localization algorithms (PDM, 4-Multihop, i-Multihop, and MDS-MAP). To reduce the influence of outliers, we run each simulation 100 times and take the average results as the final data points. The ALE is normalized by the nodes' communication (or ranging) radius R:

ALE = \frac{1}{Q R} \sum_{u = P + 1}^{P + Q} {‖ X_{u} - X_{u}^{r} ‖}_{2} \times 100 %,

(15)

where

X_{u}^{r}

is the real coordinates of normal node

N_{u}

5.1. Distribution of Node Localization Errors

Firstly, we analyze the distribution of node localization errors in the default environments. Figure 5 with log-scale y-axis presents the distribution boxplots of node localization errors. It can be seen that the localization performance of t-Multihop method is much affected by UBs. t-Multihop gives an average error of 50.24% and a median error of 44.37%, and its maximum outlier even reaches 254.92%. Compared with t-Multihop, both RMLA1 and RMLA2 have significant improvement in localization accuracy. Among them, RMLA2 performs better. Its average, median, and maximum errors are respectively 28.54%, 27.64%, and 68.18% (compared with 35.35%, 32.17%, and 103.72% of RMLA1). As RMLA1 employs the simple average method to calculate the integrated trust values of beacons, its evaluation results are worse than those of RMLA2, which further leads to the reduction of its localization accuracy. However, the performance of RMLA1 is much better than that of t-Multihop.

Figure 5

Distribution boxplots of node localization errors.

5.2. Impact of UB Number

In this part, we investigate the effects of UB number on localization accuracies of t-Multihop, RMLA1, and RMLA2. The statistics for ALEs of three methods is shown in Figure 6. With the increase of UB number, the ALEs of t-Multihop and RMLA1 rise obviously, while that of RMLA1 remains stable (nearly a horizontal line when the UB number is no more than 11). When there are 5 UBs, the ALE of t-Multihop is more than 40% (compared with about 30% of both RMLA methods). The performance of RMLA1 is almost the same as that of RMLA2 when UBs are less (no more than 5). However, the ALE of RMLA1 exceeds 40% when UB number reaches 10, while that of RMLA2 is still about 30%. Therefore, RMLA2 is more robust to UBs for WSN multihop localization, especially there are more UBs. When UB number is 12 (i.e., 40% of beacons are unreliable), the ALE of RMLA2 is still less than 40% of nodes' communication radius.

Figure 6

ALE versus UB number.

5.3. Impact of Network Connectivity

We vary nodes' communication radius and get the accuracy comparisons of three methods under different network connectivity, ranging from 11 to 23 (see Figure 7). Generally, the probability that a shortest path between a pair of nodes is close to a straight line grows as the node densities increase, which directly results in the improvement of localization accuracy. So the ALEs of three methods decline with the network connectivity increasing. But both RMLA methods always produce more accurate results. Compared with t-Multihop, RMLA1 and RMLA2 improve the localization accuracy by at least 13% and 17%, respectively. When the network connectivity is 11, the accuracy improvement of RMLA2 even reaches more than 25%. In RMLA, through trust evaluation among nodes, the beacons (reliable or unreliable) with low local densities to which the shortest paths are generally winding lines would be given lower trust degrees, which further lowers the influence of multihop distance estimation errors on node localization. Therefore, the RMLA algorithm also has positive effects on dealing with the uncertainties in multihop estimative distances.

Figure 7

ALE versus network connectivity.

5.4. Impact of Ranging Error

Figure 8 shows the comparison results of ALEs under different standard derivations λ of ranging errors. It can be seen that both RMLA methods always perform much better than t-Multihop. The accuracy improvements of RMLA1 and RMLA2 are respectively about 15% and more than 20%. When $λ \leq 5$ , the variation trend of ALEs of three methods are not very distinct. That is because the multihop distance estimation errors mainly arise from the approximations between the lengths of the shortest paths and the Euclidean distances when the ranging errors are small. Constant network connectivity makes the multihop distance estimation errors relatively stable. When λ increases to 6, the direct ranging errors begin to play a leading role in the distance estimation uncertainties. From this point ( $λ = 6$ ), all ALEs of three methods rise gradually with λ increasing. Among them, RMLA2 has better inhibition effect on ranging errors. When $λ \geq 7$ , compared with t-Multihop, RMLA2 can improve the localization accuracy by more than 30%.

Figure 8

ALE versus ranging error.

5.5. Impact of Network Topology

In this part, we analyze the impact of irregular network topology on the performance of three methods. Figure 9 shows a typical anisotropic network in which sensor nodes are randomly distributed in a C-shape spatial area. We still use the default parameters in Table 1. The only difference is that the value of TTL is set to 4 for longer shortest paths are more susceptible to concave shapes. Figure 10 presents the result of accuracy comparisons. Since the shortest path between pairwise distant nodes in irregular networks is generally more winding than that in uniform networks, the ALEs of three methods in Figure 10 are bigger than those in Figure 6. However, RMLA still performs consistently much better than t-Multihop. Compared with RMLA2, the irregular network topology has more significant influence on the performance of RMLA1 and t-Multihop of which the ALEs rise sharply with UB number increasing. When the UB number is no more than 10, the ALE curve of RMLA2 approaches to a horizontal line (always less than 40%). When the UB number reaches 11, the accuracy of RMLA2 begins to decrease markedly, but it is still superior to those of RMLA1 and t-Multihop.

Figure 9

Network topology (anisotropic network).

Figure 10

ALE versus UB number (anisotropic network).

5.6. Comparison of RMLA and Other Typical Algorithms

Finally, we evaluate the localization performance of RMLA by comparing it with three typical multihop algorithms (1) the 4-Multihop algorithm [14], (2) the PDM algorithm [15], (3) the i-Multihop algorithm [18], and one representative centralized algorithm, MDS-MAP [12], in the isotropic network shown in Figure 4 and the anisotropic network shown in Figure 9. Figures 11–13 present the comparison results when the UB ratios are 0%, 10%, and 20%, respectively (i.e., the UB numbers are 0, 3, and 6). As can be seen from Figure 11, when there is no UB, i-Multihop gives the best accuracy, PDM comes second, and MDS-MAP performs the worst. In isotropic networks, the ALEs of RMLA1, RMLA2, t-Multihop, and 4-Multihop are nearly equivalent (about 27%), while in anisotropic networks the ALE of 4-Multihop is about 4% lower than those (about 29%) of the other three algorithms. When 10% UBs exist in WSNs (see Figure 12), the performance of PDM declines most significantly (its ALEs in both networks are more than 60%). This is because the erroneous information provided by UBs severely affects the feature extraction of PDM, which further leads to the failure of multihop localization. 4-Multihop and i-Multihop also have a marked decrease in accuracy, especially in anisotropic networks. In Figure 12, RMLA2 performs the best, and its accuracy is comparable with that in Figure 11. MDS-MAP is less affected by UBs, but its ALE is still much higher than those of the other algorithms except PDM. With the increase of UB number, the advantage of RMLA2 becomes more obvious (see Figure 13). In isotropic networks, compared with 4-Multihop, PDM, i-Multihop, and MDS-MAP, it can improve localization accuracy by 48%, 88%, 29%, and 20%, respectively. In anisotropic networks, the gaps can reach 38%, 89%, 57%, and 52%. From Figures 11–13, we can conclude that the RMLA algorithms have better performance in resistance against UBs than the other five solutions. It is worth noting that RMLA2 is more efficient in anisotropic networks.

Figure 11

Performance comparison of various algorithms (no UB).

Figure 12

Performance comparison of various algorithms (10% UBs).

Figure 13

Performance comparison of various algorithms (20% UBs).

6. Conclusions

In this paper, we address the problem of node multihop localization in large-scale wireless sensor networks with unreliable beacons. Based on trust evaluation and evidence theory, we present a robust multihop localization algorithm, called RMLA, which is shown to be able to effectively mitigate the influence of UBs on the position estimation of normal nodes and improve WSN localization accuracy. In the phase of evidence combination, both the average method and the enhanced D-S combination method can be utilized to calculate the integrated trust values of beacons. The average method is simple and requires less computation cost, it is very suitable to sensor nodes with low computing power. As the D-S method makes full use of the uncertainty information in trust evaluation values, it produces more accurate results than the average method, especially there are more UBs in WSNs. In practice, we should make a reasonable tradeoff between localization accuracy and computation cost to determine which method to be adopted. Through simulations, we demonstrate that RMLA performs much better than some existing localization solutions. In isotropic networks, RMLA could achieve robust multihop localization even if 40% of beacons are unreliable. In anisotropic networks, the ratio can also reach more than 30%. Additionally, RMLA has the advantages in resistance against uncertainties in both multihop estimative distances and direct ranging results. In our future work, we will construct a more accurate BPA function related to specific network environment and implement the RMLA algorithm on experimental WSN prototypes to verify its practicability.

Footnotes

Acknowledgments

The authors would like to thank the anonymous reviewers for their comments. This paper is supported by the National Natural Science Foundation of China (NSFC) under Grants no. 60974121 and no. 61001138.

References

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

A survey on sensor networks

IEEE Communications Magazine 2002 40 8 102 114

2-s2.0-0036688074

10.1109/MCOM.2002.1024422

Buratti

Conti

Dardari

Verdone

An overview on wireless sensor networks technology and evolution

Sensors 2009 9 9 6869 6896

2-s2.0-70350023385

10.3390/s90906869

Bekmezci

Alagöz

Energy efficient, delay sensitive, fault tolerant wireless sensor network for military monitoring

International Journal of Distributed Sensor Networks 2009 5 729 747

Hamel

Chwastek

Garcia

Farouk

Kam

Dandekar

K. R.

Sensor placement for urban homeland security applications

International Journal of Distributed Sensor Networks 2010 2010 15

2-s2.0-79952838573

10.1155/2010/859263

859263

Alemdar

Durmus

Ersoy

Wireless healthcare monitoring with RFID-enhanced video sensor networks

International Journal of Distributed Sensor Networks 2010 2010 10

2-s2.0-79952848122

10.1155/2010/473037

473037

Trigoni

Krishnamachari

Sensor network algorithms and applications introduction

Philosophical Transactions of the Royal Society A 2012 370 1958 5 10

Boukerche

Oliveira

H. A. B. F.

Nakamura

E. F.

Loureiro

A. A. F.

Localization systems for wireless sensor networks

IEEE Wireless Communications 2007 14 6 6 12

2-s2.0-37249061709

10.1109/MWC.2007.4407221

Mao

Fidan

Anderson

B. D. O.

Wireless sensor network localization techniques

Computer Networks 2007 51 10 2529 2553

2-s2.0-34247885928

10.1016/j.comnet.2006.11.018

Erol-Kantarci

Mouftah

H. T.

Oktug

A survey of architectures and localization techniques for underwater acoustic sensor networks

IEEE Communications Surveys and Tutorials 2011 13 3 487 502

2-s2.0-79952835301

10.1109/SURV.2011.020211.00035

10.

Čapkun

Hubaux

J. P.

Secure positioning in wireless networks

IEEE Journal on Selected Areas in Communications 2006 24 2 221 232

2-s2.0-33144454801

10.1109/JSAC.2005.861380

11.

Boukerche

Oliveira

H. A. B. F.

Nakamura

E. F.

Loureiro

A. A. F.

Secure localization algorithms for wireless sensor networks

IEEE Communications Magazine 2008 46 4 96 101

2-s2.0-42649116160

10.1109/MCOM.2008.4481347

12.

Shang

Ruml

Zhang

Fromherz

M. P. J.

Localization from mere connectivity

Proceedings of the 4th International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC ′03)

June 2003

Annapolis, Md, USA

201 212

2-s2.0-0242612017

13.

Niculescu

Nath

DV based positioning in Ad Hoc networks

Telecommunication Systems 2003 22 1–4 267 280

2-s2.0-0038703640

10.1023/A:1023403323460

14.

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

Fort Lauderdale, Fla, USA

184 193

2-s2.0-20344364148

15.

Lim

Hou

J. C.

Localization for anisotropic sensor networks

Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′05)

March 2005

Miami, Fla, USA

138 149

16.

Cheng

K. Y.

Lui

K. S.

Tam

HyBloc: localization in sensor networks with adverse anchor placement

Sensors 2009 9 1 253 280

2-s2.0-59249088163

10.3390/s90100253

17.

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 networkss

Proceedings of IEEE Vehicular Technology Conference (VTC ′05)

May 2005

Stockholm, Sweden

2551 2555

18.

Wang

Xiao

Sensor localization in concave environments

ACM Transactions on Sensor Networks 2008 4 1, article 3 1 31

2-s2.0-41849116645

10.1145/1325651.1325654

19.

Severi

Abreu

Dardari

A quantitative comparison of multihop localization algorithms

Proceedings of the 7th Workshop on Positioning, Navigation and Communication (WPNC ′10)

March 2010

Dresden, Germany

200 205

2-s2.0-78651424941

10.1109/WPNC.2010.5653925

20.

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

2-s2.0-77956976158

10.1109/TMC.2010.129

21.

Lee

Kim

Determination of communication range for range-free multi-hop localization in wireless sensor networks

Proceedings of 20th International Conference on Computer Communications and Networks (ICCCN ′11)

July 2011

Maui, Hawaii, USA

1 4

22.

Guo

X. L.

Y. F.

Wan

J. W.

Application of BP neural network to 3D localization in wireless sensor networks

Chinese High Technology Letters 2011 21 5 471 477

2-s2.0-79959252932

10.3772/j.issn.1002-0470.2011.05.005

23.

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

24.

Zhou

Cui

J. H.

Zhou

Localization for large-scale underwater sensor networks

Lecture Notes in Computer Science 2007 4479 108 119

2-s2.0-37249048875

0644190

25.

Hong

Lim

Song

Unified modeling language based analysis of security attacks in wireless sensor networks: a survey

KSII Transactions on Internet and Information Systems 2011 5 4 805 821

2-s2.0-79956200557

10.3837/tiis.2011.04.010

26.

Kuo

S. P.

Kuo

H. J.

Tweng

Y. C.

The beacon movement detection problem in wireless sensor networks for localization applications

IEEE Transactions on Mobile Computing 2009 8 10 1326 1338

2-s2.0-70349295609

10.1109/TMC.2009.15

27.

Fan

R. F.

Jiang

S. H.

Zhang

N. T.

Ranging error-tolerable localization in wireless sensor networks with inaccurately positioned anchor nodes

Wireless Communications and Mobile Computing 2009 9 5 705 717

2-s2.0-66649121739

10.1002/wcm.623

28.

Guo

Y. J.

Anchor global position accuracy enhancement based on data fusion

IEEE Transactions on Vehicular Technology 2009 58 3 1616 1623

2-s2.0-60449096341

10.1109/TVT.2008.928636

29.

Srirangarajan

Tewfik

A. H.

Luo

Z. Q.

Distributed sensor network localization using SOCP relaxation

IEEE Transactions on Wireless Communications 2008 7 12 4886 4895

2-s2.0-58149114571

10.1109/T-WC.2008.070241

30.

Vemula

Bugallo

M. E.

Djurić

P. M.

Sensor self-localization with beacon position uncertainty

Signal Processing 2009 89 6 1144 1154

2-s2.0-60749100001

10.1016/j.sigpro.2008.12.019

31.

Lui

K. W. K.

W. K.

H. C.

Chan

F. K. W.

Semi-definite programming algorithms for sensor network node localization with uncertainties in anchor positions and/or propagation speed

IEEE Transactions on Signal Processing 2009 57 2 752 763

2-s2.0-60549110264

10.1109/TSP.2008.2007916

32.

Srinivasan

Teitelbaum

DRBTS: distributed reputation-based beacon trust system

Proceedings of the 2nd IEEE International Symposium on Dependable, Autonomic and Secure Computing (DASC ′06)

September 2006

Indianapolis, Ind, USA

277 283

2-s2.0-36949013183

10.1109/DASC.2006.28

33.

Park

Shin

K. G.

Attack-tolerant localization via iterative verification of locations in sensor networks

Transactions on Embedded Computing Systems 2008 8 1, article 2

2-s2.0-67549148698

10.1145/1457246.1457248

34.

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

35.

Jadliwala

Zhong

Upadhyaya

Qiao

C. M.

Hubaux

J. P.

Secure distance-based localization in the presence of cheating beacon nodes

IEEE Transactions on Mobile Computing 2010 9 6 810 823

36.

Shafer

A Mathematical Theory of Evidence 1976

Princeton, NJ, USA

Princeton University Press

37.

Foy

W. H.

Position-location solutions by Taylor-series estimation

IEEE Transactions on Aerospace and Electronic Systems 1976 12 2 187 194

2-s2.0-0016930753

38.

Wan

J. W.

Feng

R. J.

Y. F.

C. M.

Localization refinement for wireless sensor networks

Computer Communications 2009 32 13-14 1515 1524

2-s2.0-67650569241

10.1016/j.comcom.2009.05.011

Robust Multihop Localization for Wireless Sensor Networks with Unreliable Beacons

Abstract

1. Introduction

2. Related Works

2.1. Multihop Localization Studies

2.2. Unreliable Beacon-Tolerant Localization Studies

3. Preliminaries

3.1. Problem Formulation

3.2. Related Definitions

4. Robust Multihop Localization Algorithm

4.1. Trust Evaluation Framework

4.2. Trust Evaluation among Beacons

4.3. Calculation of Integrated Trust Values

4.4. Weighted Estimation of Node Coordinates

4.5. Discussion of RMLA Algorithm

5. Performance Evaluation

5.1. Distribution of Node Localization Errors

5.2. Impact of UB Number

5.3. Impact of Network Connectivity

5.4. Impact of Ranging Error

5.5. Impact of Network Topology

5.6. Comparison of RMLA and Other Typical Algorithms

6. Conclusions

Footnotes

Acknowledgments

References