Two-hop distance estimation in wireless sensor networks

Abstract

In wireless sensor networks, the accurate estimation of distances between sensor nodes is essential. In addition to the distance information available for immediate neighbors within a sensing range, the distance estimation of two-hop neighbors can be exploited in various wireless sensor network applications such as sensor localization, robust data transfer against hidden terminals, and geographic greedy routing. In this article, we propose a two-hop distance estimation method, which first obtains the region in which the two-hop neighbor nodes possibly exist and then takes the average of the distances to the points in that region. The improvement in the estimation accuracy achieved by the proposed method is analyzed in comparison with a simple summation method that adds two single-hop distances as an estimate of a two-hop distance. Numerical simulation results show that in comparison with other existing distance estimation methods, the proposed method significantly reduces the distance estimation error over a wide range of node densities.

Introduction

Wireless sensor networks (WSNs) have been widely researched and are now actively being applied to numerous areas, such as environmental sensing, health-care monitoring, industrial monitoring, and military networking. ¹ Usually, WSNs are composed of a number of sensor nodes with limited sensing, computing, and communicating capabilities. Each sensor node collaborates with others in sensing, detecting, and tracking events of interests. For example, in military applications, such as battlefield surveillance, sensor nodes are capable of detecting military objects using various sensors (e.g. acoustic, vibration, and motion). If an event is triggered by a sensor in a sensor node, it reports the acquired data of the event to a sink node, usually stamped with the time and location information. Using the reported information from multiple sensor nodes, the position and speed of the target object can be inferred. In health-care monitoring applications, sensor nodes can be used for monitoring vital signs of patients in a hospital. As sensor nodes are attached to each individual patient, the position of the patient is directly obtained by the location of the sensor. If the sensor node provides accurate location information in an emergency, the patient can be found in a short time. Since the location information of sensor nodes is directly and indirectly exploited for the purposes of sensor network applications, how each sensor node obtains its accurate position is one of the most important research issues and many efforts have been made to improve the localization accuracy.

Localization algorithms for WSNs can be divided into two major types: range-free localization and range-based localization.^2,3 Range-free localization algorithms usually do not require direct information about the distance or angle between the nodes. They only need to deploy a few anchor nodes in the network for obtaining information about the connectivity or distance between anchor nodes and a small number of sensor nodes. Many range-free localization algorithms, such as connectivity-based localization^4,5 and centroid-based localization,^6,7 have been studied. Even though the range-free localization algorithms are cost-effective, they usually provide less accuracy than the range-based localization algorithms. Range-based localization algorithms generally provide better accuracy, but additional hardware is required to implement ranging techniques such as time of arrival (ToA), received signal strength indication (RSSI), or chirp spread spectrum (CSS). Using the distance measured by a ranging technique, the location of nodes can be determined by exploiting the multilateration algorithm, ⁸ multidimensional scaling (MDS) scheme, ⁹ or semi-definite programming (SDP) algorithm. ¹⁰ To achieve high accuracy of localization, accurate distance estimation is essential in both kinds of localization algorithms, because the localization of sensor nodes is performed using the estimated distance information if the distance between nodes cannot be directly measured. For example, in range-free localization algorithms, connectivity-based localizations exploiting distance vector (DV)-hop or hop-count need to estimate the distances between a few anchor nodes in order to calculate the expected hop-progress or average hop-size. Range-based localization algorithms require more precise distance estimation because the estimated distances between nodes are directly utilized to calculate the location of the nodes. For instance, the multilateration algorithm in the work by Zhou et al. ⁸ necessarily requires accurate information about the distance from anchor nodes to the target sensor node to solve an optimization problem. In the work by Shang and Rum, ⁹ the MDS-based localization scheme combines single-hop and two-hop distance information into a distance matrix to build a map of the relative locations of nodes. While the single-hop distance can be easily measured in most cases with the help of advanced ranging techniques, the two-hop distance cannot be directly carried out by ranging techniques, and it is approximated by a simple summation of two single-hop distances. As a result, considerable error may be introduced, and consequently, the accuracy of localization is reduced.

Many researchers have developed two-hop distance estimation methods in various ways to improve accuracy. Most of them attempted to characterize the relationship between the hop-count and the geographic distance among nodes (i.e. per-hop distance). Note that the two-hop distance is obtained by two times per-hop distance. In the work by Quanrui et al., ¹¹ the incongruity of the assumption in typical DV-hop-based distance estimation methods is highlighted, which presume that the hop-size is always the same regardless of hop-count. The authors analyzed the relationship between hop-size and hop-count and proposed a new hop-size estimation method, which works much better in dense networks. In the work by Choi and Ma, ¹² a two-hop distance estimation algorithm, which considers both range-based and connectivity-based information, has been proposed. However, the drawback of this approach is that both types of information are not exploited concurrently, but one of them is selectively used depending on the network condition. Song and Tam ¹³ proposed to take the average of hop-sizes obtained for all anchor nodes as a hop-size of unknown node instead of that obtained for the anchor node that is the closest one to the unknown node. However, this approach may give a poor estimate of per-hop distance in anisotropic sensor networks if an appropriate refinement postprocessing is not performed. Zhipeng et al. ¹⁴ have proposed twice weighted DV-hop (TWDV-hop) algorithm to balance the global and local topological characteristics in estimation of per-hop distance. Each anchor node first computes the average per-hop distance to all the other anchor nodes locally and then the global per-hop distance is calculated by a weighted sum of the local per-hop distances. The per-hop distance between nodes is estimated using a weighted sum of the local and global per-hop distances with different weights depending on network topology conditions.

In addition, density-aware hop-progress estimation schemes have also been studied.^15–17 Wang et al. ¹⁵ have proposed the localization algorithm using expected hop progress (LEAP) with respect to the node density of the network, in which nodes are randomly distributed by the Poisson point process. In this approach, the multihop distance is simply calculated as the product of the expected hop-progress and hop-counts. To apply the distance estimation in an environment similar to the real network more appropriately, a multihop distance estimation algorithm using the local expected hop length (LEHL) has been considered by Myint et al. ¹⁶ In contrast with LAEP, which uses the average node density of the network, LEHL exploits the local node density to improve the distance estimation accuracy even for a nonuniformly deployed topology. Ma et al. ¹⁷ have proposed a source-to-sink distance estimation scheme that exploits the correlation between the source-to-sink distance and the hop-counts of source node’s neighbors to the sink. They formulated the source-to-sink distance estimation as a constrained optimization that minimizes the discrepancy between the actual number and the expected number of source node’s neighbors for different hop-counts to the sink when the node density is given.

In this article, we consider an estimation of the two-hop distance in WSNs where every single-hop distance between neighbor nodes is assumed to be easily obtained by any kind of ranging technique. We propose a two-hop distance estimation method, which first obtains the region in which the two-hop neighbor nodes possibly exist and then takes the average of the distances to the points in that region in order to reduce the average estimation error of the two-hop distance. To examine the extent of improvement in the estimation accuracy achievable by the proposed method, a mathematical analysis is performed to compare the estimation accuracy of the proposed method with that of a simple-sum method that adds two single-hop distances as an estimate of a two-hop distance. Through numerical simulations, we verify that the two-hop distance estimated by the proposed method significantly improves accuracy over a wide range of node densities compared to the distances obtained by other existing distance estimation methods.

The remainder of this article is organized as follows. In section “Two-hop distance calculation model,” we first describe a calculation model for two-hop distance estimation. We then propose a two-hop distance estimation method in section “Proposed two-hop distance estimation method.” The performance evaluation is carried out in section “Performance evaluation,” and section “Conclusion” concludes this article.

Two-hop distance calculation model

We consider an estimation of the two-hop distance in WSNs, in which each node is assumed to be capable of measuring the distance to its single-hop neighbor node using a ranging technique. Figure 1 shows an example in which the nodes i and j are two-hop neighbors, and the nodes k and l are the relay nodes between the nodes i and j. Each node i, j, k, and l have the radio range of $R_i$ , $R_j$ , $R_k$ , and $R_l$ , respectively. It is assumed that the nodes within the radio range of each other are considered as single-hop neighbors. In the figure, $d_{\mathrm{ij}}$ is the two-hop distance between the nodes i and j, while $d_{\mathrm{il}}$ , $d_{\mathrm{ik}}$ , $d_{\mathrm{lj}}$ , and $d_{\mathrm{kj}}$ are the single-hop distances that can be directly measured using a ranging device. Since both nodes k and l are located within the radio range of the node i as well as the node j, the distances between single-hop neighbors, that is, $d_{\mathrm{ik}}$ , $d_{\mathrm{kj}}$ , $d_{\mathrm{il}}$ , and $d_{\mathrm{lj}}$ , are assumed to be measured by a ranging device. With the single-hop distances available, the two-hop distance $d_{\mathrm{ij}}$ from node i to node j can be calculated using the law of cosines as follows:

$$\begin{array}{cc}\multicolumn{1}{c}{d_{\mathrm{ij}}=}& \sqrt{d_{\mathrm{ik}}^2+d_{\mathrm{kj}}^2-2d_{\mathrm{ik}}{d}_{\mathrm{kj}}\cos {\theta }_k}\hfill \\ \multicolumn{1}{c}{=}& \sqrt{d_{\mathrm{il}}^2+d_{\mathrm{lj}}^2-2d_{\mathrm{il}}{d}_{\mathrm{lj}}\cos {\theta }_l}\hfill \end{array}$$

(1)

where ${\theta }_k$ and ${\theta }_l$ are the angles between $d_{\mathrm{ik}}$ and $d_{\mathrm{kj}}$ and between $d_{\mathrm{il}}$ and $d_{\mathrm{lj}}$ , respectively. However, it is not possible to accurately obtain the value of ${\theta }_k$ and ${\theta }_l$ when the nodes are not equipped with an angle-of-arrival (AoA) measurement device.

Figure 1.

Illustration of two-hop distance estimation.

In many cases, a simple-sum method is used to estimate the two-hop distances because of its simplicity. The simple-sum method chooses the shortest path among all possible paths between two-hop neighbor nodes and then the two-hop distance is approximately given by the summation of single-hop distances on that path. For example, in Figure 1, the two-hop distance between nodes i and j estimated by applying the simple-sum method is given by

$$d_{\mathrm{sum}}=\min \{d_{\mathrm{ik}}+d_{\mathrm{kj}},d_{\mathrm{il}}+d_{\mathrm{lj}}\}$$

(2)

Note that the two-hop distance obtained by the simple-sum method provides the maximum bound of two-hop distance for a given set of two single-hop distances, that is, $d_{\mathrm{ij}}=d_{\mathrm{ik}}+d_{\mathrm{kj}}$ only when ${\theta }_k=180\circ$ . Therefore, the simple-sum method may lead to a considerable distance error depending on the difference between the actual value of ${\theta }_k$ and $180\circ$ . In other words, the error in two-hop distance estimated by the simple-sum method, which can be given by $d_{\mathrm{error}}=|d_{\mathrm{ij}}-d_{\mathrm{sum}}|$ , is highly dependent on ${\theta }_k$ . The simple-sum method gives the accurate estimate when ${\theta }_k=180\circ$ , and the estimate becomes less accurate as ${\theta }_k$ decreases.

Proposed two-hop distance estimation method

In this section, we propose a two-hop distance estimation method, which first computes an arc that the two-hop neighbor nodes possibly exist on and then takes the average distance to the circumference of the arc in order to reduce the estimation error of two-hop distance on average.

First, we consider a region in which the two-hop neighbor nodes of a reference node are expected to exist. Figure 2 shows a situation in which the node i (reference node) and node j are two-hop neighbors, and node k is the relay node between the nodes i and j. Here, since nodes i and k are single-hop neighbors and nodes k and j are single-hop neighbors, the distances $d_{\mathrm{ik}}$ and $d_{\mathrm{kj}}$ are obtainable by a ranging device. Given $R_i$ , $d_{\mathrm{ik}}$ , and $d_{\mathrm{kj}}$ , an arc centered at node k with a radius of $d_{\mathrm{kj}}$ can be drawn as shown in Figure 2. Note that the arc is a set of all possible points that two-hop neighbor node j may exist on. The central angle of the arc is given by

$$\begin{array}{c}{\theta }_{\mathrm{arc}}=2\pi -2\mathrm{co}{\mathrm{s}}^{-1}\left(\frac{{d_{\mathrm{ik}}}^2+{d_{\mathrm{kj}}}^2-{R_i}^2}{2d_{\mathrm{ik}}{d}_{\mathrm{kj}}}\right)\hfill \\ =2\mathrm{co}{\mathrm{s}}^{-1}\left(\frac{{R_i}^2-{d_{\mathrm{ik}}}^2-{d_{\mathrm{kj}}}^2}{2d_{\mathrm{ik}}{d}_{\mathrm{kj}}}\right)\hfill \end{array}$$

(3)

because any point on the arc cannot be included in the circle centered at the node i with radius $R_i$ . If a point is included in the circle, the distance to the node i is smaller than $R_i$ and it becomes single-hop neighbor rather than two-hop neighbor of the node i.

Figure 2.

Proposed two-hop distance estimation method using an arc in which the two-hop neighbor nodes possibly exist.

To estimate the two-hop distance, we propose to take the average of all possible expected distances between nodes i and j as the final two-hop distance, which is given by

$$d_{\mathrm{prop}}=\frac{1}{{\theta }_{\mathrm{arc}}}\underset{\pi -\frac{{\theta }_{\mathrm{arc}}}{2}}{\overset{\pi +\frac{{\theta }_{\mathrm{arc}}}{2}}{\int }}\sqrt{{d_{\mathrm{ik}}}^2+{d_{\mathrm{kj}}}^2-2d_{\mathrm{ik}}{d}_{\mathrm{kj}}\cos {\theta }_k}d{\theta }_k$$

(4)

Because of its symmetry, we can simply consider only the top part of the arc. Finally, the two-hop distance estimated using the proposed method is given by

$$\begin{array}{c}{d}_{\mathrm{prop}}=\frac{2}{{\theta }_{\mathrm{arc}}}\underset{\pi -\frac{{\theta }_{\mathrm{arc}}}{2}}{\overset{\pi }{\int }}\sqrt{{d_{\mathrm{ik}}}^2+{d_{\mathrm{kj}}}^2-2d_{\mathrm{ik}}{d}_{\mathrm{kj}}\cos {\theta }_k}d{\theta }_k\hfill \end{array}$$

(5)

In summary, for given two single-hop distances, $d_{\mathrm{ik}}$ and $d_{\mathrm{kj}}$ , and the radio range of reference node i, $R_i$ , we compute ${\theta }_{\mathrm{arc}}$ by equation (3) and then obtain the two-hop distance estimate by taking the average of two-hop distances to the points on the arc by equation (5).

To intuitively see the extent of improvement in the accuracy of the two-hop distance estimation brought about by the proposed method, we compare the range of the arc that achieves higher accuracy using the proposed method with the range of the arc that achieves higher accuracy using the simple-sum method. In Figure 2, $d_{\mathrm{prop}}$ denotes the two-hop distance estimated by the proposed two-hop distance estimation method, and $d_{\mathrm{sum}}$ is the two-hop distance estimated using the simple-sum method. As shown in Figure 2, we divide the arc into two segments by a threshold distance, which determines which of the two methods mentioned above estimates the two-hop distance more accurately. The threshold distance $d_{\mathrm{thr}}$ can simply be given by

$$\begin{array}{c}{d}_{\mathrm{thr}}=\frac{d_{\mathrm{prop}}+d_{\mathrm{sum}}}{2}\hfill \\ =\frac{d_{\mathrm{ik}}+d_{\mathrm{kj}}}{2}\hfill \\ +\frac{1}{{\theta }_{\mathrm{arc}}}\underset{\pi -\frac{{\theta }_{\mathrm{arc}}}{2}}{\overset{\pi }{\int }}\sqrt{{d_{\mathrm{ik}}}^2+{d_{\mathrm{kj}}}^2-2d_{\mathrm{ik}}{d}_{\mathrm{kj}}\cos {\theta }_k}d{\theta }_k\hfill \end{array}$$

(6)

The proposed two-hop distance estimation method gives higher accuracy if node j exists on the blue-colored segment in Figure 2. However, if node j exists on the segment indicated by a green diagonal pattern, the simple-sum method gives a more accurate estimate of the two-hop distance.

Now, the accuracy of the proposed two-hop distance estimation method is evaluated by comparing the lengths of the two segments of the arc. If the blue-colored segment of the arc is longer than the segment with a green diagonal pattern, the proposed method provides more accurate estimation results on average. Since the length of an arc is proportional to its corresponding central angle, the relation between ${\theta }_{\mathrm{prop}}$ and ${\theta }_{\mathrm{sum}}$ is investigated. If ${\theta }_{\mathrm{prop}}$ is always larger than ${\theta }_{\mathrm{sum}}$ , it implies that the proposed two-hop distance estimation method would, on average, give a higher accuracy than the simple-sum method.

Theorem 1. ${\theta }_{\mathrm{prop}}$ is always larger than ${\theta }_{\mathrm{sum}}$ .

Proof. We define ${\theta }_{\Delta }=({\theta }_{\mathrm{prop}}-{\theta }_{\mathrm{sum}})$ , where ${\theta }_{\mathrm{prop}}=({\theta }_{\mathrm{arc}}/2-2\alpha )$ and ${\theta }_{\mathrm{sum}}=2\alpha$ . This proof shows ${\theta }_{\Delta }>0$ . For convenience of analysis, we simply assume that the single-hop distances, $d_{\mathrm{ik}}$ and $d_{\mathrm{kj}}$ , are equal and denote them by $R·x$ as shown in Figure 3 (i.e. $d_{\mathrm{ik}}=R·x$ and $d_{\mathrm{kj}}=R·x$ ). Note that x can vary from 1/2 to 1, that is, $1/2<x\le 1$ .

Figure 3.

Illustration of the relation between ${\theta }_{\mathrm{prop}}$ and ${\theta }_{\mathrm{sum}}$ for Theorem 1.

Under the assumption, ${\theta }_{\Delta }$ can be rewritten as follows:

$$\begin{array}{c}{\theta }_{\Delta }(x)=\pi -2\mathrm{si}{\mathrm{n}}^{-1}\left(\frac{1}{2x}\right)-4\mathrm{co}{\mathrm{s}}^{-1}\left(\frac{d_{\mathrm{thr}}(x)}{2\mathrm{Rx}}\right)\hfill \\ =2\mathrm{co}{\mathrm{s}}^{-1}\left(\frac{1}{2x}\right)-4\mathrm{co}{\mathrm{s}}^{-1}\left(\frac{d_{\mathrm{thr}}(x)}{2\mathrm{Rx}}\right)\hfill \end{array}$$

(7)

where

$$\begin{array}{cc}{d}_{\mathrm{thr}}(x)\hfill & =\mathrm{Rx}+\frac{\sqrt{2}\mathrm{Rx}}{{\theta }_{\mathrm{arc}}}\underset{\pi -\frac{{\theta }_{\mathrm{arc}}}{2}}{\overset{\pi }{\int }}\sqrt{1-\cos {\theta }_k}d{\theta }_k\hfill \\ \multicolumn{1}{c}{}& =\mathrm{Rx}(1+\frac{2\sqrt{1-\frac{1}{4x^2}}}{\mathrm{co}{\mathrm{s}}^{-1}(\frac{1}{2x^2}-1)})\hfill \end{array}$$

(8)

Then, ${\theta }_{\Delta }$ can be rewritten as a function of x as follows:

$${\theta }_{\Delta }(x)=2\mathrm{co}{\mathrm{s}}^{-1}\left(\frac{1}{2x}\right)-4\mathrm{co}{\mathrm{s}}^{-1}(\frac{1}{2}+\frac{\sqrt{1-\frac{1}{4x^2}}}{\mathrm{co}{\mathrm{s}}^{-1}(\frac{1}{2x^2}-1)})$$

(9)

It can be numerically shown that ${\theta }_{\Delta }(x)$ in equation (9) is an increasing function of x, and it is positive for $x\in (1/2,1]$ as shown in Figure 4. Hence, ${\theta }_{\mathrm{prop}}$ is always larger than ${\theta }_{\mathrm{sum}}$ .

Figure 4.

Plot of ${\theta }_{\Delta }(x)$ with respect to x.

To examine whether the proposed method outperforms the simple-sum method in more realistic scenarios, we compute the ratio of ${\theta }_{\mathrm{prop}}$ to ${\theta }_{\mathrm{sum}}$ with respect to single-hop distances $d_{\mathrm{ik}}$ and $d_{\mathrm{kj}}$ . We now assume that $d_{\mathrm{ik}}$ and $d_{\mathrm{kj}}$ are independently varying (i.e. $d_{\mathrm{ik}}=R·x_1$ and $d_{\mathrm{kj}}=R·x_2$ ). Note that since $0<x_1\le 1$ , $0<x_2\le 1$ , and $x_1+x_2>1$ , $x_1+x_2$ can vary from 1 to 2, that is, $1<x_1+x_2\le 2$ . In Figure 5, it is seen that ${\theta }_{\mathrm{prop}}/{\theta }_{\mathrm{sum}}$ is always greater than 1; the minimum value is 1.45 when $x_1=0.5$ and $x_2=0.5$ , and the maximum value is 1.56 at around $x_1=1$ and $x_2=0$ , or $x_1=0$ and $x_2=1$ . This definitely implies that the proposed two-hop distance estimation method can give higher accuracy than the simple-sum method on an average, because ${\theta }_{\mathrm{prop}}$ is always larger than ${\theta }_{\mathrm{sum}}$ for any value of $x_1$ and $x_2$ in the range.

Figure 5.

Ratio of ${\theta }_{\mathrm{prop}}$ to ${\theta }_{\mathrm{sum}}$ with respect to $x_1$ and $x_2$ .

Performance evaluation

To evaluate the performance of the proposed two-hop distance estimation method, we consider a WSN in which the nodes are distributed according to the Poisson point process with a node density $\lambda$ in a two-dimensional space of 100 m × 100 m area. Note that the node density is represented by the average number of nodes in 100 m² area. Every single-hop distance between nodes is obtainable in advance through ranging techniques such as ToA, RSSI, and CSS. In real WSN environments, the accuracy of single-hop distance ranging is susceptible to various measurement noises such as radio frequency channel fading in RSSI-based ranging and clock synchronization error in ToA-based ranging. In the simulations, this single-hop distance ranging error is modeled as an unbiased uniform distribution with ± 5% error.

$P_{\mathrm{prop}}$ with respect to $\lambda$

First, we examine the probability that the proposed two-hop distance estimation method provides a more accurate estimate of two-hop distance than the simple-sum method. Let $P_{\mathrm{prop}}$ denote the probability that the proposed method outperforms the simple-sum method. Then, the probability that the simple-sum method provides more accurate two-hop distance estimation than the proposed method is given by $P_{\mathrm{sum}}=1-P_{\mathrm{prop}}$ . Figure 6 shows the simulation result when the node density $\lambda$ varies from $\lambda =0.1$ (nodes are “barely” connected) to $\lambda =1$ (nodes are “densely” connected). It is seen that $P_{\mathrm{prop}}$ increases and the gap between $P_{\mathrm{prop}}$ and $P_{\mathrm{sum}}$ increases as $\lambda$ increases. Here, it is noteworthy that $P_{\mathrm{prop}}$ is always higher than 0.5 in the whole range of $\lambda$ .

Figure 6.

Simulation results of $P_{\mathrm{prop}}$ and $P_{\mathrm{sum}}$ with respect to node density $\lambda$ .

Distance estimation error with respect to $\lambda$ and R

We perform the Monte Carlo simulations to compute two-hop distance estimation error of the proposed method and compare it with those of the following methods:

• Simple-sum method given by equation (2) in section “Two-hop distance calculation model.”

• Two-hop distance estimation method by Choi and Ma: ¹² It calculates two upper bounds of the angle at a relay node using ranging and connectivity information. Two-hop distance is obtained using the minimum one of two bounds.

• TWDV-hop-based method by Zhipeng et al.: ¹⁴ It computes the global and local per-hop distances, and the distance between nodes is obtained using the weighted summation of two per-hop distances.

• LEHL-based distance estimation by Myint et al.: ¹⁶ When the expected hop length is calculated, LEHL exploits the local information about node density and node connectivity, whereas LAEP utilizes only the average node density and average node connectivity of the whole network. In the LEHL-based method, the two-hop distance is estimated from the sum of two expected local hop lengths, which may be different from each other in terms of the local node density or local connectivity.

The reported values of the simulation results represent the average of 10,000 runs. In the figures, the vertical line indicates the 95% confidence interval of each experiment.

We first examine the average two-hop distance estimation error with respect to $\lambda$ . Figure 7 shows the simulation results when the radio range of every node is fixed at 30 m. From the figure, it is observed that the proposed method exhibits the lowest two-hop distance estimation error for any value of $\lambda$ . However, the simple-sum method shows the worst accuracy. This is because the simple-sum method always provides the maximum value among all the possible estimated two-hop distances, which can lead to a considerable error, as mentioned in section “Two-hop distance calculation model.” The other three methods show similar estimation performances in Figure 7. Among the three methods, TWDV-hop-based method shows the worst accuracy when $\lambda$ is low, but it gradually overwhelms the other two methods as $\lambda$ increases. Furthermore, it is seen that the two-hop distance estimation error of the proposed method decreases at a rate slightly greater than simple-sum method as $\lambda$ increases. Note that the results of this simulation are consistent with the results of the simulation in section “ $P_{\mathrm{prop}}$ with respect to $\lambda$ ” in that the proposed method, on an average, can provide a lower distance error than the simple-sum method, and the accuracy slowly improves as $\lambda$ increases.

Figure 7.

Two-hop distance estimation error with respect to node density $\lambda$ when $R_i$ = 30 m.

Next, we perform the simulations for the scenario where each node has a different radio range. The radio range is determined by a uniform distribution in [10, 50] m. In Figure 8, it is seen that the confidence intervals are much wider than those in Figure 7. This is due to the randomness in the radio ranges of the nodes. The proposed method provides the smallest distance error among the five methods, while the simple-sum method gives the largest error. Among the three methods, LEHL-based method provides the best performance. It implies that LEHL can achieve more robust estimation performance than the other two methods in the situation in which each node has a different radio range.

Figure 8.

Two-hop distance estimation error with respect to node density $\lambda$ when $R_i$ = [10, 50] m.

We evaluate the average two-hop distance estimation error with respect to the radio range. Note that the radio range of nodes may change depending on path loss characteristics in real network environments. In this simulation, the radio range varies from 20 to 50 m because of different path loss exponents, and it also follows a Gaussian random distribution with the standard deviation $\sigma$ of 1 m. The node density $\lambda$ is fixed at 0.4. In Figure 9, a comparison between the performances of the five methods produces results similar to those observed in the previous figures, that is, the proposed method for two-hop distance estimation produces the smallest error whereas the simple-sum method produces the highest error among the five methods, regardless of the value of $R_i$ . It can also be seen that all five methods provide linearly increasing values of distance error as $R_i$ increases.

Figure 9.

Two-hop distance estimation error with respect to $R_i$ when $\lambda =0.4$ .

Energy cost issue

We consider the energy efficiency of two-hop distance estimation. For a given distance R, the proposed method estimates the distances to other nodes within two-hop distance $2R$ instead of directly measuring the distance by increasing the radio range to $2R$ . This would result in a significant decrease in power consumption at each node in comparison with the case that each node directly measures the two-hop distance $2R$ by a ranging device.

To examine how much transmit power is saved by two-hop distance estimation, we compute the transmit powers to increase the radio distance from R to $2R$ . Figure 10 shows the ratio of the transmit power for $2R$ radio distance to that for R with respect to path loss exponent $\alpha$ . For $\alpha$ = 2, four times higher transmit power is required for the direct measurement of two-hop distance $2R$ , and it exponentially increases as $\alpha$ increases. This indicates that two-hop distance estimation is more desirable for WSNs with battery-powered sensor nodes even though there exists a certain level of estimation errors in comparison with the direct measurement–based two-hop ranging.

Figure 10.

Ratio of transmit power for $2R$ radio distance to that for R with respect to path loss exponent $\alpha$ .

Conclusion

In this article, we considered a method for the estimation of the distance between two-hop neighbor nodes in WSNs. Under the assumption that the single-hop distance information of every pair of nodes is available in the network, we proposed a method that estimates two-hop distances by taking the average of all possible expected two-hop distances as the final estimated distance. A mathematical analysis of the comparison between the proposed method and the simple-sum-based estimation provided a reasonable expectation of the significant improvement in accuracy achieved by the proposed two-hop distance estimation method. Results of the numerical simulations confirmed that the accuracy of two-hop distance estimated using the proposed method is significantly increased over a wide range of node densities in a network.