Sage Journals: Discover world-class research

Abstract

In order to improve the localization accuracy of distance vector-Hop algorithm under the random topology network scenarios, a novel algorithm named coordinates correction-distance vector-Hop is proposed. Coordinates correction-distance vector-Hop defines the pseudo-range error factor to improve the accuracy of average hop distance. In order to improve the localization accuracy, the unknown node uses distances to part of anchor nodes to locate. Furthermore, anchor nodes are treated as unknown when obtaining their coordinate correction values which are used to correct the localization results of unknown nodes. The simulation results show that each step of coordinates correction-distance vector-Hop can increase the localization accuracy effectively; coordinates correction-distance vector-Hop is better than the traditional distance vector-Hop and some existing improved algorithms both in localization accuracy and in localization stability.

Keywords

Wireless sensor networks distance vector-Hop node localization average hop distance pseudo-range error factor

Introduction

Wireless sensor networks (WSNs) are composed of plenty of sensor nodes deployed in the monitoring field. A multi-hop self-configured network can be further formed by means of wireless communication.¹ The sensor nodes with perception, processing, and communication ability need to locate themselves not only for reporting events but also for the target tracking in many applications. Examples include environmental monitoring, medical care, and military target tracking services. Sensory data will make no significance without the position information in many applications. Hence, node localization is a key issue of WSNs, and accurate and stable localization algorithm is essential for WSNs.

Currently, many localization algorithms have been proposed to calculate the position of individual nodes. Based on the criteria whether it requires to measure the actual distances between nodes, the localization algorithms of WSNs can be classified into two categories, that is, range-based and range-free schemes. The range-based algorithms, such as time difference of arrival (TDOA),² received signal strength (RSS),³ angle of arrival (AOA),⁴ and time of arrival (TOA),⁵ need to use the distance or angle information between neighbors to locate, and some of them may even need precise clock synchronization. These algorithms present very accurate results. However, the specialized hardware required makes them expensive in large networks, and in some applications, these algorithms are greatly influenced by the surrounding environment, which has limited the application of such methods to some extent. Due to the limitations of hardware and restrictions on high power consumption of the range-based algorithms, the rang-free algorithms, such as centroid algorithm,⁶ approximate point-in-triangulation (APIT),⁷ distance vector-Hop (DV-Hop),⁸ and multidimensional scaling-map (MDS-MAP),⁹ are recommended as they use the estimated distance instead of the metrical distance to locate. In terms of accuracy, the range-free algorithms are not as good as those based on range, but they can still satisfy a number of applications’ requirements. With the advantages of relatively simple implementation, low power consumption, and low cost, rang-free algorithms are being pursued as a feasible alternative to the range-based algorithms in large-scale practical applications.

The DV-Hop algorithm, as a range-free localization algorithm, aims to use the connectivity information to compute the shortest paths and the average hop distance (AHD) applied by the unknown nodes to obtain the estimated distances to anchors.¹⁰ Then, those estimated distances and anchor locations are used as inputs in trilateration to locate unknown nodes. Since actual locations of the anchors are known, the major source of localization error comes from the AHD calculation. If the distribution of nodes across the network is uniform, DV-Hop can obtain a reasonable AHD, so as to achieve the appropriate positioning accuracy.¹¹ On contrary, as the networks where the nodes are disposed stochastically, the AHD is always bigger than the actual due to the shortest paths may be not straight-line between anchor nodes and unknown nodes.¹² In such cases, using the hopping distance to replace the straight-line distance will cause a larger error and unsatisfactory positioning accuracy. Hence, an efficient way to improve the calculation accuracy of AHD has a crucial impact on distance estimated and localization accuracy.

In this article, we propose an improved DV-Hop algorithm named coordinates correction-DV-Hop (CC-DV-Hop). First, the pseudo-range error factor is defined to remove anchor nodes which may cause a larger calculation error of the AHD, through this way to improve the calculation accuracy of AHD, as well as to reduce the influence of random topology. Second, the anchor node broadcasts the corrected AHD together with its corrected coordinate values calculated by trilateral or multilateral measurement with the premise of being treated as the unknown node. Finally, the coordinates of each unknown node are corrected through the weighted average value of the coordinate correction values which are received from the corresponding anchors. We also present the simulations to demonstrate the effectiveness of CC-DV-Hop.

The rest of this article is organized as follows. Section “Related work” gives a survey of the related works. Section “DV-Hop localization algorithm” describes the original DV-Hop algorithm. Section “CC-DV-Hop algorithm” presents the derivation of the proposed improved algorithm—CC-DV-Hop. In section “Simulation results and discussion,” simulation results are shown and localization performances are discussed. In section “Conclusion,” conclusions are presented.

Related work

Since the AHD and the hop-count between the destination and the anchor nodes have essential impact on the localization accuracy of traditional DV-Hop algorithm, a number of approaches have been studied to improve the accuracy of AHD and hop-count.

It is often considered that algorithms increase the accuracy of the AHD based on the selection of anchor nodes. Gui et al.¹³ checked out DV-Hop algorithm and proposed the selective three-anchor DV-Hop algorithm. In this algorithm, the normal node first selects any three anchors to form a three-anchor group; then, it calculates the candidate position based on each three-anchor group; finally, according to the relation between candidate positions and the minimum hop anchor nodes, the normal node chooses the best candidate position. Wang et al.¹⁴ calculated and optimized the coordinates of the unknown node that was set as the anchor node to increase the anchor node density, so as to improve the localization accuracy of DV-Hop. Xia et al.¹⁵ proposed an improved algorithm based on regional division of hop-count. The received signal strength indication (RSSI) location technology and the hop-limitation mechanism are introduced to optimize the combination of anchor nodes to determine the coordinates of unknown nodes.

Some previous works improve the accuracy of the AHD by weighting method. Hu and Li¹⁶ used a hop threshold M that limits the unknown nodes to receive the beacon nodes with M hops. Then, the AHD is calculated using the weighting method, and the distances between nodes are also calculated to improve the localization precision under the limitation of M hops. Zhang et al.¹⁷ introduced the weighted mean method to calculate the AHD. Instead of trilateration method, the centroid method is used to calculate the coordinate. Hou et al.¹⁸ proposed differential DV-Hop (DDV-Hop) algorithm to improve the AHD applied by each locating node for estimating its own location through weighting the N received AHD from anchor nodes. The results show that DDV-Hop algorithm has higher localization accuracy compared with DV-Hop algorithm and Hop-count algorithm.

However, some studies have been made on the correction of hop-count. Zhang et al.¹⁹ proposed RSSI and average hopping distance modifying DV-Hop (RADV-Hop) algorithm through using RSSI to subdivide one hop into several grades and modify AHD to reduce the locating error. Wen et al.²⁰ subdivided the first hop into several grades based on RSSI. The rest hops are modified to achieve higher location precision than traditional DV-Hop algorithm with the distance ratio of adjacent nodes which is transformed into the corresponding relationship of RSSI. Xiao and Liu²¹ refined and made sure the hops between anchor nodes were not only integer but also decimal between all anchor nodes and unknown nodes. Simulation results show that it has obviously better localization performance in positioning accuracy than the traditional DV-Hop algorithm.

Recently, considering the need of high localization accuracy along with energy consumptions has become a research hotspot. Kumar and Lobiyal²² proposed a power-efficient range-free localization algorithm (PERLA) for WSNs. In PERLA, the anchor node floods packet just once, and one complete communication is eliminated to reduce the energy consumption. To improve the localization results of unknown nodes, PERLA adopts a new procedure to reduce error propagation. Simulation results show that PERLA is more computationally efficient and localization performance is superior to the traditional DV-Hop algorithm. Li²³ proposed an improved DV-Hop localization algorithm based on energy-saving non-ranging optimization. In this algorithm, only one anchor node broadcasts its position coordinate information to other node, thus reducing the energy consumption. To improve the localization accuracy, non-ranging energy-saving optimization algorithm is used to locate unknown nodes and the ratio of position is used to reduce the localization error. Simulation results show that compared with the traditional DV-Hop, the proposed algorithm has better results in localization accuracy and energy-solving performance. Liu et al.²⁴ restricted the hop-counts between unknown nodes and anchors to reduce the energy consumption. Moreover, they use the scheme of upgrading positioned nodes and a new weighted average one-hop distance processing method to guarantee the localization accuracy. Simulation and analysis results show that the new algorithm can effectively decrease the positioning error and total localization rounds to take account of both the energy consumption and the localization accuracy.

DV-Hop localization algorithm

The original DV-Hop algorithm is a distributed, hop-by-hop localization algorithm. The algorithm implementation is composed of three non-overlapping stages.

In the first phase, each anchor node broadcasts a message to be flooded throughout the network which contains its location information and a hop-count parameter initialized to zero. Each receiving node maintains a table $(x_{i}, y_{i}, ho p_{i})$ , where $x_{i}$ and $y_{i}$ are the coordinates of anchor nodes it received and $ho p_{i}$ is the minimum hop-count to the particular anchor node. If a received message contains lower hop-count to a particular anchor node, the corresponding item in the table will be replaced by the information in this message. And this message is flooded outward with hop-count values incremented by one. On contrary, if a received message contains a higher hop-count to a particular anchor node, this message will be ignored. Through this mechanism, all nodes in the network get the minimal hop-count to every anchor node.

In the second phase, once an anchor $i$ gets location and hop-count to other anchor nodes, the AHD of anchor $i$ is estimated as in equation (1)

HopSiz e_{i} = \frac{\sum_{j \neq i} \sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2}}}{\sum_{j \neq i} h_{ij}}

(1)

where $(x_{i}, y_{i})$ and $(x_{j}, y_{j})$ are the coordinates of anchor $i$ and anchor $j$ , respectively; $HopSiz e_{i}$ is the estimated AHD of anchor $i$ ; and $h_{ij}$ is the hop-count between anchor $i$ and anchor $j$ .

Once the $HopSiz e_{i}$ is calculated, each anchor node broadcasts its $HopSiz e_{i}$ to the network with controlled flooding. Unknown nodes receive $HopSiz e_{i}$ information and only save the first one. They transmit the $HopSiz e_{i}$ to their neighbor nodes at the same time. This scheme could assure that most nodes receive the $HopSiz e_{i}$ from the anchor node that has the least hops between them. When an unknown node $u$ accepts the information from one anchor node, it computes the distance between itself and the anchor node as in the following formula

d_{uk} = HopSiz e_{i} \times ho p_{uk}

(2)

where $ho p_{uk}$ is the minimum hop-count between the unknown node $u$ and the anchor node $k$ and $HopSiz e_{i}$ is the AHD that the unknown node $u$ obtains from the nearest anchor node.

In the third phase, each unknown node location can be estimated by the polygon method. Let $(x_{u}, y_{u})$ be the unknown node $u$ location, $(x_{i}, y_{i})$ be the known location of the ith anchor node receiver, and $d_{i}$ be the ith anchor node distance to the unknown node $u$ . We suppose that $n$ sensors are to determine the location of unknown node. Then, the unknown node $u$ location can be acquired by equation (3)

{\begin{matrix} {(x_{u} - x_{1})}^{2} + {(y_{u} - y_{1})}^{2} = d_{u 1}^{2} \\ {(x_{u} - x_{2})}^{2} + {(y_{u} - y_{2})}^{2} = d_{u 2}^{2} \\ \cdot \\ \cdot \\ \cdot \\ {(x_{u} - x_{n})}^{2} + {(y_{u} - y_{n})}^{2} = d_{un}^{2} \end{matrix}

(3)

The system is solved to use a standard least-squares approach by the following formula

A = [\begin{matrix} 2 (x_{1} - x_{n}) \\ 2 (x_{2} - x_{n}) \\ \cdot \\ \cdot \\ \cdot \\ 2 (x_{n - 1} - x_{n}) \end{matrix} \begin{matrix} 2 (y_{1} - y_{n}) \\ 2 (y_{2} - y_{n}) \\ \cdot \\ \cdot \\ \cdot \\ 2 (y_{n - 1} - y_{n}) \end{matrix}]

(4)

B = [\begin{matrix} x_{1}^{2} - x_{n}^{2} + y_{1}^{2} - y_{n}^{2} + d_{un}^{2} - d_{u 1}^{2} \\ x_{2}^{2} - x_{n}^{2} + y_{2}^{2} - y_{n}^{2} + d_{un}^{2} - d_{u 2}^{2} \\ \cdot \\ \cdot \\ \cdot \\ x_{n - 1}^{2} - x_{n}^{2} + y_{n - 1}^{2} - y_{n}^{2} + d_{un}^{2} - d_{u (n - 1)}^{2} \end{matrix}]

(5)

U = [\begin{matrix} x_{u} \\ y_{u} \end{matrix}] = {(A^{T} A)}^{- 1} A^{T} B

(6)

CC-DV-Hop algorithm

In this section, we use the traditional DV-Hop algorithm to calculate the initial AHD of each anchor node and propose to use the following additional steps added in order to improve localization accuracy, thus forming CC-DV-Hop algorithm.

Correction of AHD

Under the premise of DV-Hop idea, the number of hops among nodes is generally fixed. In order to obtain the minimum error between the estimated distance and the actual distance, CC-DV-Hop manages to adjust the AHD. According to the second phase of DV-Hop introduced in section “DV-Hop localization algorithm,” there will be a big error that each anchor node selects all the other anchors as the reference nodes to estimate an AHD, because some of them may produce a large error especially in the random topology networks. Therefore, CC-DV-Hop provides an approach to remove the reference anchors which may produce a large error through this way to improve the calculation accuracy of AHD.

First, we define pseudo-range error factor of each anchor node to its reference nodes. For example, anchor $N_{i}$ calculates the pseudo-range error factor to the jth reference anchor as follows

diff_er r_{ij} = | \frac{{\tilde{d}}_{ij} - d_{ij}}{d_{ij}} |

(7)

where $d_{ij}$ and ${\tilde{d}}_{ij}$ are the actual distance and the estimated distance between anchor $N_{i}$ and anchor $N_{j}$ , respectively. And ${\tilde{d}}_{ij}$ can be calculated by

{\tilde{d}}_{ij} = HopSiz e_{i} \times ho p_{ij}

(8)

where $ho p_{ij}$ is the hop-count between anchor $N_{i}$ and anchor $N_{j}$ and $HopSiz e_{i}$ is the average hop size of anchor $N_{i}$ .

The smaller the value of $diff_er r_{ij}$ , the closer the pseudo-range to the real distance. Then, we sort $diff_er r_{ij}$ in ascending order and choose the top $k (k \geq 3)$ reference anchors to form an optimal group of anchors ( $OGA s_{i, k}$ ) of $N_{i}$ to recalculate the AHD of $N_{i}$ by equation (9). Finally, $N_{i}$ uses ${HopSize}_{i}^{k}$ to replace $HopSiz e_{i}$ as its AHD

{HopSize}_{i}^{k} = \frac{\sum_{j = 1}^{k} d_{ij}}{\sum_{j = 1}^{k} ho p_{ij}}

(9)

Calculation of the coordinate correction value of anchor nodes

Supposing anchor $N_{i}$ is an unknown node, $N_{i}$ locates itself by estimating its distances to each anchor among $OGA s_{i, k}$ . The distance between $N_{i}$ and the jth $(1 \leq j \leq k)$ anchor node $N_{j}$ within $OGA s_{i, k}$ is calculated by equation (10)

{\tilde{d}}_{ij} = {HopSize}_{i}^{k} \times ho p_{ij}

(10)

Since true location of $N_{i}$ is known, we can calculate the position correction values of $N_{i}$ by equation (11)

{\begin{matrix} Δ x_{i} = x_{i} - {\tilde{x}}_{i} \\ Δ y_{i} = y_{i} - {\tilde{y}}_{i} \end{matrix}

(11)

where $(x_{i}, y_{i})$ and $({\tilde{x}}_{i}, {\tilde{y}}_{i})$ are the actual and estimated coordinates of $N_{i}$ , respectively. In a similar manner, each anchor node can obtain its corrected AHD and coordinate correction values. Afterwards, each anchor node broadcasts its message packages to its neighbors with controlled flooding. The format of the package is ${ID, OGA s_{i, k}, {HopSize}_{i}^{k}, (Δ x_{i}, Δ y_{i})}$ .

In the example in Figure 1, we assume that all nodes are deployed randomly across the network.

After the first step of DV-Hop, anchor 1 calculates its AHD $(HopSiz e_{1})$ based on the distances and hops from itself to its neighbors and obtain the estimated distance to other anchors by equation (8). After that, we calculate the pseudo-range error factors of anchor 1 to reference nodes by equation (7).

We sort the pseudo-range error factors in ascending order and select the top $k$ reference nodes to form $OGA s_{i, k}$ of anchor 1. Here, we set $k = 5$ and assume that anchors 2–6 are selected as the $OGA s_{1, 5}$ .

Anchor 1 adopts equation (9) to acquire the corrected AHD $({HopSize}_{1}^{5})$ and uses ${HopSize}_{1}^{5}$ to calculate the distances to each reference node among $OGA s_{1, 5}$ to obtain its estimated position (E1). Afterwards, anchor 1 uses equation (11) to calculate its coordinate corrections. In a similar manner, each anchor node can obtain its corrected AHD and coordinate correction values. Then, anchor 1 broadcasts its message packages to neighbors and the format is ${ID = 1, OGA s_{1, 5}, {HopSize}_{1}^{5}, (Δ x_{1}, Δ y_{1})}$ .

Figure 1.

The concept of sections “Correction of AHD” and “Calculation of the coordinate correction value of anchor nodes.”

Optimization of the coordinates of unknown nodes

As what we have introduced above, in DV-Hop, unknown nodes take the nearest anchor’s AHD as their own, so do they in CC-DV-Hop. However, different from DV-Hop, an unknown node uses the distances to each reference node among its nearest anchor node’s $OGAs$ to locate in CC-DV-Hop. For example, unknown node $n_{u}$ uses ${HopSize}_{i}^{k}$ received from its nearest anchor $N_{i}$ to estimate the distances to each anchor among $OGA s_{ik}$ and then uses trilateration to acquire the estimated coordinate $({\tilde{x}}_{u}, {\tilde{y}}_{u})$ .

In WSNs, the nodes in close proximity have very similar physical environment (e.g. the electromagnetic environment, the multi-path effect, and interference noise) and topological structure. Therefore, if each unknown node and its nearest anchor node use the same $OGAs$ to estimate their own coordinates, the coordinate correction values of them are similar. So, it is reasonable that the unknown node’s coordinates are corrected by its nearest anchor node’s coordinate correction values. Moreover, since the correction values of nodes obey Gaussian distribution under the topology random networks, the anchor node with the closer distance has a greater effect on the positioning accuracy of the unknown node. Thus, we define weights $p_{i} = 1 / ho p_{ui}$ ( $ho p_{ui}$ is the hop-count between anchor $N_{i}$ and unknown node $n_{u}$ , $N_{i}$ within $OGA s_{i, k}$ ) to ensure the closest anchor node that will mostly affect the localization result. Then, we modify the coordinates of $n_{u}$ by equation (12). And $(x_{u}, y_{u})$ is the final estimated coordinates of $n_{u}$

{\begin{matrix} x_{u} = {\tilde{x}}_{u} + \frac{1}{k} \sum_{i = 1}^{k} p_{i} Δ x_{i} \\ y_{u} = {\tilde{y}}_{u} + \frac{1}{k} \sum_{i = 1}^{k} p_{i} Δ y_{i} \end{matrix}

(12)

Continue the example in Figure 1 and the example in Figure 2, suppose that we need to estimate the position of unknown node U. We assume that anchor node 1 is the nearest anchor node of unknown node U.

Unknown node U receives message package from anchor node 1. Then, U uses ranges between U and each anchor node among OGAs_1,5 to calculate the estimated coordinates U1 (shown in Figure 2(a)).

Finally, the coordinates of U1 and the coordinate correct values of OGAs_1,5 are used as inputs in equation (12) to acquire the localization result U2 (shown in Figure 2(b)).

Figure 2.

The concept of correcting estimated coordinates: (a) locating unknown node U and (b) correcting U’s estimated position.

Simulation results and discussion

Assuming nodes with the same communication radius are randomly distributed in the square region area with the fixed size of 150 × 150 m², and we use Matlab2013a as the simulator to evaluate the performance of algorithm. The metric for comparison in evaluating localization algorithms is the average location error, which is shown as follows

a v e_e r r o r = \sum_{i = 1}^{n} \frac{\sqrt{{(x_{i} - X_{i})}^{2} + {(y_{i} - Y_{i})}^{2}}}{n \times R} \times 100 %

(13)

where $(x_{i}, y_{i})$ is the estimated coordinates, $(X_{i}, Y_{i})$ is the actual coordinates, $R$ is the communication radius, and $n$ is the number of unknown nodes. In all of our graphs, each data point represents the average value of 200 trials with different random seeds.

Validation of the improved effect in each step

In this section, two new algorithms named CC-DV-Hop_1 and CC-DV-Hop_2 were proposed. For CC-DV-Hop_1 algorithm, only use the method in section “Correction of AHD” to correct the AHD and then use the procedure same as DV-Hop to locate unknown node. For CC-DV-Hop_2 algorithm, different with CC-DV-Hop, the last step (uses the coordinate correction values of anchor nodes to correct the coordinates of unknown nodes) of CC-DV-Hop is not employed. Compared to the localization results of the traditional DV-Hop with CC-DV-Hop_1, CC-DV-Hop_2, and CC-DV-Hop, we can learn the improved effect in each step of CC-DV-Hop. And the simulation results are given as follows.

Figure 3 shows the comparison of the average localization errors in four algorithms. As shown in Figure 3(a), with the increase in ratio of anchors, the average localization accuracy of CC-DV-Hop_1 is about 10% lower than DV-Hop, that of CC-DV-Hop_2 is about 20% lower than DV-Hop, and that of CC-DV-Hop is about 5% lower than CC-DV-Hop_2; as shown in Figure 3(b), with the increase in node number, the average localization accuracy of CC-DV-Hop_1 is about 15% lower than DV-Hop, that of CC-DV-Hop_2 is about 17% lower than DV-Hop, and that of CC-DV-Hop is about 5% lower than CC-DV-Hop_2; as shown in Figure 3(c), with the increase in communication radius of anchor node, the average localization accuracy of CC-DV-Hop_1 is about 13% lower than DV-Hop, that of CC-DV-Hop_2 is about 15% lower than DV-Hop, and that of CC-DV-Hop is about 3% lower than CC-DV-Hop_2. It is obvious that CC-DV-Hop_1 can improve the localization accuracy of traditional DV-Hop, CC-DV-Hop_2 can do it better than CC-DV-Hop_1, and CC-DV-Hop can achieve the best localization accuracy. We can conclude that each step (e.g. correct the AHD and locate unknown node by nearest anchor’s $OGAs$ and the correct unknown node’s coordinates) of CC-DV-Hop can effectively improve the localization accuracy.

Figure 3.

Localization error of DV-Hop, CC-DV-Hop_1, CC-DV-Hop_2, and CC-DV-Hop in different networks: (a) comparison with different ratios of anchor (300 nodes, R = 20 m), (b) comparison with different node numbers (ratio of anchor = 30%, R = 20 m), and (c) comparison with different anchor node communication radii (200 nodes, ratio of anchor = 30%).

Analysis of localization accuracy

In this section, CC-DV-Hop is compared with the traditional DV-Hop, the algorithm in Xiao and Liu,²¹ and DDV-Hop in Hou et al.¹⁸ We set $k = ⌊ N / 3 ⌋$ in CC-DV-Hop (the reason for setting can be seen in section “Analysis of localization accuracy”).

Varying the ratio of anchors

In this scenario, 200 nodes (including anchor nodes) are randomly distributed in the sensor area. Vary the ratio of anchors from 0.05 to 0.45 and set the communication radius of each node as 20 m.

Figure 4 shows the comparison of the average localization errors in four algorithms. We can see that the average localization errors of these four algorithms above tend to decline gradually when the anchor is in 5%–25% ratio and become stable when the anchor ratio is greater than 25%. Under the same condition, the average localization error of CC-DV-Hop is about 24% lower than that of the traditional DV-Hop, about 4% lower than that of DDV-Hop, and about 10% lower than that of literature²¹ algorithm. The reason is that the growth of the ratio of anchor nodes will reduce the distance between unknown nodes and the anchor nodes, decrease the information loss, and lead to a relatively high accuracy. Moreover, with the increase in anchor ratio, each anchor node has more reference nodes to choose to form more precise $OGAs$ . Therefore, CC-DV-Hop can improve the localization accuracy better.

Figure 4.

Comparison with different ratios of anchor.

Varying node number

In this scenario, the anchor ratio is set as 30% and communication radius is set as 20 m, and the node number is increased from 100 to 400.

Figure 5 shows the contrast of four algorithms with different node numbers. To a certain extent, we observe that DDV-Hop and the algorithm in Xiao and Liu²¹ improve the accuracy of the DV-Hop, while the CC-DV-Hop improves the accuracy on a much larger scale. The accuracy improvement of CC-DV-Hop is about 5% over than that of DDV-Hop, about 6% over than that of the algorithm in Xiao and Liu,²¹ and about 24% over than that of the traditional DV-Hop. We can conclude that CC-DV-Hop has better localization precision than the other three and is more stable for its fluctuation range smaller than the other three algorithms with the variety of node numbers. The reason is that the increase in node number will change the network topology which may affect the localization accuracy of DV-Hop. However, CC-DV-Hop only selects $k$ reference nodes with lower pseudo-range error factors to recalculate the AHD and others are removed, so as to reduce the influence of random topology. Therefore, the number of nodes has little influence on the location accuracy and stability of CC-DV-Hop.

Figure 5.

Comparison with different node numbers.

Varying communication radius

In this scenario, the ratio of anchor nodes is set as 30%, node number is set as 300, and the communication radius of anchor node is increased 5 m every time.

Figure 6 shows that the average localization error of CC-DV-Hop is approximately 22% lower than that of the DV-Hop, approximately 4% lower than that of DDV-Hop, and approximately 3% lower than that of the algorithm in Xiao and Liu.²¹ It is worth mentioning that the algorithm in Xiao and Liu²¹ has better accuracy than DDV-Hop when the communication radius is larger than 35 m; however, CC-DV-Hop performs better in those environments. We conclude that the change in communication radius has minimal impact on CC-DV-Hop, which means CC-DV-Hop has better stability. The reason is that the AHD is always bigger than the actual distance, especially under random network. Normally, the greater the number of hops is, the greater accumulative error in the AHD calculation is and the bigger pseudo-range error factors are according to equation (2). The node’s communication radius will change the network connectivity, so as to influence hops between nodes and the AHD calculation. CC-DV-Hop removes some reference nodes with bigger pseudo-range error factor to reduce the accumulative errors in the distance estimated through this way to increase the accuracy of AHD calculation. Furthermore, fewer nodes participating in the AHD recalculation would reduce the computational complexity as well.

Figure 6.

Comparison with different anchor node communication radii.

Discussion about the value of k

In CC-DV-Hop, the value of $k$ is the key factor in the relationship between localization accuracy and energy consumption. If $k$ is too small, the improvement of positioning accuracy may not be obvious enough although the computational complexity can be reduced. If the value of $k$ is too large, it will lead overmuch reference nodes to be used for modifying AHD and cause a waste of sensor node resource. So, it is not good for the value of $k$ to get too big or too small, and we must choose the $k$ value suitably according to the actual situation of network. In this section, we investigate the effect of the value of $k$ on the localization accuracy via extensive simulations.

Figure 7 shows the effect of value of k on localizaiton accuracy. We can see that as a whole, when $3 \leq k \leq ⌊ N / 3 ⌋$ , the localization accuracy appears an increasing trend; when $⌊ N / 3 ⌋ \leq k \leq ⌊ N / 2 ⌋$ , the localization accuracy appears the most excellent; and when $⌊ N / 2 ⌋ \leq k \leq N$ , the localization accuracy appears a decreasing trend. Therefore, when $⌊ N / 3 ⌋ \leq k \leq ⌊ N / 2 ⌋$ , CC-DV-Hop algorithm obtains the optimal localization accuracy.

Figure 7.

Effect of the value of k on localization accuracy.

Discussion about performance

For communication cost, the proposed CC-DV-Hop algorithm does not change the positioning process of the DV-Hop, and sense node does not require additional communication cost. Therefore, the communication cost of CC-DV-Hop is nearly the same as DV-Hop, the algorithm in Xiao and Liu,²¹ and DDV-Hop. For the computational complexity, in CC-DV-Hop, anchor nodes only use the information of anchor nodes in the DV-Hop to calculate the corrected AHD and the coordinate correction values without additional hardware support, which will increase the computational complexity. However, less anchor nodes involved in the location of unknown node will decrease the computational complexity of CC-DV-Hop. Although the computational complexity of CC-DV-Hop is slightly higher than DV-Hop, it greatly improves positioning accuracy (about 25%–35%) and stability of DV-Hop. Compared with the algorithm in Xiao and Liu²¹ and DDV-Hop, CC-DV-Hop improves the localization accuracy about 8% and 5% in the case of almost the same complexity.

Conclusion

In this article, CC-DV-Hop has been presented to enhance the positioning accuracy of DV-Hop under the random topology network scenarios. Simulation results show that the localization precision and stability of CC-DV-Hop are better than the traditional DV-Hop, DDV-Hop, and the improved algorithm in Xiao and Liu.²¹ Moreover, when $⌊ N / 3 ⌋ \leq k \leq ⌊ N / 2 ⌋$ , CC-DV-Hop algorithm obtains the optimal localization accuracy.

Future directions for this work may include reducing computational complexity for CC-DV-Hop which is the main downside of that algorithm and find the balance between localization accuracy and energy consumption.

Footnotes

Handling Editor: Roberto Casas

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (No. 41101426).

References

Akyildiz

Sankarasubramaniam

et al . Wireless sensor networks: a survey. Comput Netw 2002; 38(4): 393–422.

Cheng

Thaeler

Xue

et al . TPS: a time-based positioning scheme for outdoor wireless sensor networks. In: Proceedings of the 23rd IEEE annual joint conference of the IEEE computer and communications societies (INFOCOM ’04), Hong Kong, China, 7–11 March 2004, pp.2685–2696. New York: IEEE.

Shen

Ding

Dasgupta

et al . Multiple source localization in wireless sensor networks based on time of arrival measurement. IEEE T Signal Proces 2014; 62(8): 1938–1949.

Torrieri

DJ.

Statistical theory of passive location systems. IEEE T Aero Elec Sys 1984; 20(2): 183–198.

Girod

Estrin

Robust range estimation using acoustic and multimodal sensing. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Maui, HI, 29 October–3 November 2001, pp.1312–1320. New York: IEEE.

Bulusu

Heidemann

Estrin

. GPS-less low-cost outdoor localization for very small devices. IEEE Pers Commun 2000; 7: 28–34.

Huang

Blum

et al . Range-free localization schemes for large scale sensor networks. In: Proceedings of the 9th annual international conference on mobile computing and networking, San Diego, CA, 14–19 September 2003, pp.81–95. New York: ACM.

Niculescu

Nath

Ad hoc positioning system (APS). In: Proceedings of the IEEE global telecommunications conference (GLOBECOM ’01), San Francisco, TX, 25–29 November 2001, pp.2962–2931. New York: IEEE.

Shang

Ruml

Zhang

et al . Localization from mere connectivity. In: Proceedings of the 4th ACM international symposium on mobile ad hoc networking & communicating (MobiHoc ’03), Annapolis, MD, 1–3 June 2003, pp.201–212. New York: ACM.

10.

Qian

Shen

Chen

HP.

An improved node localization algorithm based on DV-Hop for wireless sensor networks. Comput Sci Inf Syst 2010; 8(4): 953–972.

11.

Gui

Val

Wei

et al . Improvement of range-free localization technology by a novel DV-hop protocol in wireless sensor networks. Ad Hoc Netw 2015; 24: 55–73.

12.

Song

Tam

DY.

Two novel DV-Hop localization algorithms for randomly deployed wireless sensor networks. Int J Distrib Sens N 2015; 2015: 1.

13.

Gui

Val

Wei

Improving localization accuracy using selective 3-anchor DV-Hop algorithm. In: Proceedings of the IEEE 74th vehicular technology conference (VTC full ’11), San Francisco, CA, 5–8 September 2011, pp.1–5. New York: IEEE.

14.

Wang

Hao

Wang

Choice of location-based anchor node localization algorithm for wireless sensor networks. J Comput Res Dev 2010; 47: 31–34

15.

Xia

Zou

Zhu

et al . Improved DV-Hop algorithm based on regional division of hop count. Chinese J Sens Actuators 2014; 27(7): 964–969.

16.

An improvement of DV-Hop localization algorithm for wireless sensor networks. Telecommun Syst 2013; 53: 13–18.

17.

Zhang

Liu

Wang

et al . DV-Hop localization algorithms based on centroid in wireless sensor networks. In: Proceedings of the international conference on consumer electronics, communications and networks, Yichang, China, 21–23 April 2012, pp.3216–3219. New York: IEEE.

18.

Hou

Zhou

Liu

A novel DV-Hop localization algorithm for asymmetry distributed wireless sensor networks. In: Proceedings of the 3rd IEEE international conference on computer science and information technology (ICCSIT), Chengdu, China, 9–11 July 2010, vol. 4, pp.243–248. New York: IEEE.

19.

Zhang

et al . Improved DV-Hop positioning algorithm based on one-hop subdivision and average hopping distance modification. Chinese J Sci Instrum 2012; 33(11): 2552–2559.

20.

Wen

Fan

XJ.

Improved DV-Hop location algorithm based on hop correction. Chinese J Sens Actuators 2014; 27(1): 113–117.

21.

Xiao

Liu

XH.

DV-Hop localization algorithm based on hop amendment. Chinese J Sens Actuators 2012; 25(12): 1726–1729

22.

Kumar

Lobiyal

DK.

Power efficient range-free localization algorithm for wireless sensor networks. Wirel Netw 2014; 20(4): 681–694.

23.

An improved DV-Hop localization algorithm based on energy-saving non-ranging optimization. J Netw 2014; 9(11). DOI: 10.4304/jnw.9.11.3182-3187.

24.

Liu

Zheng

Zhong

et al . Improved DV-Hop algorithm for high accuracy and low energy consumption. In: Proceedings of the IEEE computer science and automation engineering conference (CSAE), Zhangjiajie, China, 25–27 May 2012, pp.349–353. New York: IEEE.

An improved distance vector-Hop localization algorithm based on coordinate correction

Abstract

Keywords

Introduction

Related work

DV-Hop localization algorithm

CC-DV-Hop algorithm

Correction of AHD

Calculation of the coordinate correction value of anchor nodes

Optimization of the coordinates of unknown nodes

Simulation results and discussion

Validation of the improved effect in each step

Analysis of localization accuracy

Varying the ratio of anchors

Varying node number

Varying communication radius

Discussion about the value of k

Discussion about performance

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References