DV-Hop algorithm for adaptive hop-count improvement and average hop distance optimization

Abstract

In order to improve the localization accuracy of unknown nodes in DV-Hop algorithm, an improved DV-Hop algorithm combined with adaptive hop count and optimized hop distance was proposed. Our proposed algorithm firstly introduced the concept of the adaptive value for the number of communication radii. It was used to adaptively select the number of communication radii for beacon nodes and could realize the subdivision of the minimum hop count. Secondly, sensor nodes adaptively set the hop threshold to reduce the calculation. Finally, the calculation method of the average hop distance of beacon nodes was optimized and the error was corrected. The average hop distance of unknown nodes was obtained by the weighted normalization used for the average hop distance of beacon nodes. Simulation results in both random deployment environment of sensor nodes and nonrandom deployment environment of beacon nodes demonstrate that the localization accuracy of our proposed algorithm is significantly better than the DV-Hop algorithm and furthermore has better robustness and adaptability.

Keywords

Wireless sensor networks DV-Hop algorithm adaptive average hop distance weighted average

1. Introduction

Wireless Sensor Networks (WSN) is a multi-hop self-organizing network system formed by a large number of low-cost micro sensor nodes in the monitoring area through wireless communication [8]. The location information in the WSN can report the location of the incident, track the target, assist routing and manage the network, so the localization of sensor nodes is particularly important in the WSN [4]. Based on hardware requirement, the localization algorithms are mainly classified into two categories: range-based localization algorithms and range-free localization algorithms. Some of the range-based localization algorithms are: AOA algorithm, RSSI algorithm, and TDOA algorithm [16]. Some of the range-free localization algorithms are: centroid algorithm, DV-Hop algorithm, and APIT algorithm [10].

DV-Hop algorithm is a widely used localization algorithm in WSN. Because of the uneven and irregular deployment of sensor nodes in WSN, DV-Hop algorithm has low localization accuracy [14]. In order to improve the localization accuracy of the DV-Hop algorithm, many researchers have improved the DV-Hop algorithm. Y.H. Huang et al. [5] established a precise coordinates system through hop counts quantization and used an adaptive mass-spring optimization algorithm to optimize coordinates of sensor nodes. But if the precise coordinate system needs to use the measured distance information, the deployment costs will increase. On the basis of angle information, W.Y. Liu et al. [11] proposed a selective strategy of beacon codes to reduce the localization error. X. Shi et al. [13] firstly used the correction value of anchor nodes hop distance to calculate the distance between the nodes. Secondly, according to the feedback control principle, deviation analysis was carried out by membership function. Finally, the coordinate of the unknown node was corrected through twice-refinement. Their algorithm improve the localization accuracy, but the radius of network communication, the number of nodes in the radius of communication and the ratio of beacon nodes all have the certain effects on the localization performance of the algorithm. J. Li et al. [7] applied two communication radii to get more accurate hop count and improved the localization accuracy. D.G. Zhang et al. [17] presented a novel positioning service computing method to improve the efficiency of localization service. In their paper, the average hop distance of unknown nodes obtained by the unknown nodes themselves, this method solved the dependence on beacon node density. According to the intersection density among circles with beacon node as center and estimation distance as radius, the unknown node coordinates could be calculated. Z.H. Cui et al. [3] designed a novel oriented cuckoo search algorithm (OCS) to calculate the unknown node coordinates in DV-Hop algorithm. This method improves the localization accuracy but also increases the cost of computing. J. Cheng and L.Y. Xia [2] presented an effective Cuckoo Search (CS) algorithm for node localization performance based on the modification of step size and mutation probability. But there are some limitations in searching the best nest. D.F. Liu et al. [9] proposed a hybrid intelligent optimization algorithm to improve DV-Hop algorithm. It effectively improves the localization accuracy but increases the calculation cost. G. Chen et al. [1] used the local neighborhood to calculate the average hop distance and designed a novel correction scheme for localization performance. A. Kaur et al. [6] proposed a weighted centroid DV-Hop algorithm and limited the broadcasting range to reduce the localization error and energy consumption.

In order to solve the problem that DV-Hop algorithm has low localization accuracy in random deployment of sensor nodes, this paper analyzes the cause of localization error, and presents the corresponding improvement methods. We opted for adopting the adaptive hop count and hop distance optimization strategy to reduce the error between the estimated distance and the real distance of sensor nodes, and improving the localization accuracy of unknown nodes in the DV-Hop algorithm.

This paper is organized as follows. In Section 2, we state the DV-Hop algorithm and analyze the cause of localization error. In Section 3, our proposed algorithm is explained. In Section 4, the simulation results and discussion are performed. Finally, we draw our conclusions in Section 5.

2. DV-Hop algorithm and error analysis

2.1. DV-Hop algorithm

The localization process of DV-Hop algorithm can be divided into three stages:

Calculating the minimum hop count of the sensor nodes to each beacon node. Each beacon node broadcasts the packet to the neighbor nodes, which includes the location information and hop counts. The hop counts are initialized to 0. The receiving nodes record the minimum hop count from each beacon node while ignoring the other hop counts from the same beacon node. Finally, the receiving nodes add the minimum hop count to 1 and broadcast to the neighbor nodes.

Calculating the estimated distance between each unknown node and each beacon node. Setting the coordinates of beacon node i and j are $(x i, y i)$ and $(x j, y j)$ . On the basis of the location information and minimum hop counts between the beacon node and other beacon nodes in stage 1, the average hop distance of each beacon node is computed as follows: $\begin{matrix} (1) & {HopSize}_{i} = \frac{\sum_{j \neq i} \sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2}}}{\sum_{i \neq j} h_{i j}} \end{matrix}$ where $h_{i j}$ is the minimum hop count between the beacon node i and j.

Each unknown node only receive the first average hop distance which is from the beacon nodes, and broadcast to the neighbor nodes. This method makes the most of unknown nodes receive the average hop distance from the nearest beacon node. On the basis of the minimum hop count and the average hop distance, the estimated distance between each unknown node and each beacon node is calculated by: $\begin{matrix} (2) & d_{u i} = h_{u i} \times {HopSize}_{k} \end{matrix}$ where $h_{u i}$ is the minimum hop count between the unknown node u and the beacon node i, and ${Hopsize}_{k}$ is the average hop distance between the unknown node u and the nearest beacon node k.

Calculating coordinates of each unknown node by maximum likelihood estimation. Each unknown node uses maximum likelihood estimation to calculate its own coordinates based on the estimated distance in stage 2.

2.2. Error analysis

In the DV-Hop algorithm, beacon nodes broadcast their location information by flooding. In each flooding process, the location information packets of beacon nodes contain hop counts value and ID information. All the sensor nodes in the communication radius of beacon nodes can receive the location information packets, which are called the neighbor nodes. These neighbor nodes record the minimum hop count from the beacon nodes, and broadcast the packets to their neighbor nodes after increasing the minimum hop count by 1. In this method, all the sensor nodes can get the minimum hop count from each beacon node. But because of the randomness and uncertainty of the sensor nodes deployment, all the neighbor nodes can not be attached to the communication radius edge of the beacon nodes and form a circular deployment. As shown in Fig. 1, node A is a beacon node and R is a communication radius of the beacon node A, the unknown nodes are within the communication radius of the beacon node A, so they are neighbor nodes of the beacon node A, the minimum hop count is 1 between the neighbor nodes and the beacon node A. According to the DV-Hop algorithm, the estimated distances between unknown nodes in the dotted circle and the beacon node A equal the estimated distances between unknown nodes outside the dotted circle and the beacon node A. But in the Fig. 1, the real distances between unknown nodes in the dotted circle and the beacon node A are shorter than the real distance between the unknown node B and the beacon node A, the estimated distances are quite different from the real distances, therefore these estimated distances lead to the low localization accuracy in the DV-Hop algorithm. When the density of sensor nodes is higher, the number of neighbor nodes of each beacon node will increase and the number of neighbor nodes with inaccurate hop counts will also increase, which leads to the increase of the localization error.

Fig. 1.

Plot of one hop nodes deployment.

In the DV-Hop algorithm, the unknown node only uses the average hop distance of the nearest beacon node to calculate the estimated distance. But because of the irregular network topology, this method leads to the calculation error of estimated distance and is not suitable for the whole wireless sensor networks. As shown in Fig. 2, nodes B, C, D and E are beacon nodes, node A is an unknown node, we know that the average hop distance of the unknown node is equal to the average hop distance of the nearest beacon node, so the average hop distance of the unknown node A is equal to the average hop distance of the beacon node E. If the error of the average hop distance of the beacon node E is big, the accumulative error of the estimated distance of the unknown node A will increase with the increase of the minimum hop count. For example, when calculating the estimated distance between the beacon node A and the unknown node D, the accumulative error will increase and the deployment environment of the sensor nodes around the beacon node D is not considered.

Fig. 2.

Plot of nodes deployment and communication.

3. An improved DV-Hop localization algorithm

When the network topology of WSN is irregular, neighbor nodes are randomly deployed in the communication radius of the sensor node, which lead to the calculation error of the minimum hop count, and this error will increase with the increase of the node density in the network. In order to reduce the calculation error of estimated distance and improve the localization accuracy of sensor nodes, the adaptive hop count and the average hop distance optimization strategy are used to improve and optimize the DV-Hop algorithm in this paper.

3.1. Improvement of the minimum hop count for unknown nodes to each beacon node

In order to subdivide the minimum hop count of the sensor nodes, and overcome the defect that the unknown node B is far away from the beacon node A and unknown nodes in the dotted circle are close to the beacon node A but the minimum hop count of all the unknown nodes are the same in Fig. 1, beacon nodes in our proposed algorithm adopt the method of adaptive multi communication radii for flood broadcasting. The adaptive value for the number of communication radii is determined by using Eq. (3): $\begin{matrix} (3) & p = ⌈ (\frac{N_{A}}{N} + \frac{R}{L_{B}}) \times ω ⌉ \end{matrix}$ where $N_{A}$ is the number of beacon nodes, N is the number of sensor nodes, R is the communication radius of sensor nodes, $L_{B}$ is the maximum length of sensor nodes deployment area, ω is a multiplier factor, the value of multiplier factor is obtained by the beacon node density and the subdivision requirement for the minimum hop count of sensor nodes, p is the number of communication radii, and $⌈ ⌉$ is a symbol for ceiling.

The value of p is the number of communication radii of the beacon node, and is adaptively obtained by the ratio of the number of beacon nodes and the ratio of R to $L_{B}$ . When the beacon nodes ratio or the ratio of R to $L_{B}$ increases, the number of neighbor nodes increases, and then the value of p also increases, making the subdivision of the minimum hop count more accurate. When the beacon nodes ratio or the ratio of R to $L_{B}$ decreases, the number of neighbor nodes decreases, and the then the value of p also decreases, which not only ensures the subdivision of the minimum hop count, but also saves the energy of beacon nodes.

For example, when the R is 30 m, the maximum length of sensor nodes deployment area is 100 m, the beacon nodes ratio is 25%, and ω is 5, the value of p is 3, beacon nodes are broadcast with three communication radii, and three communication radii are $0.3 R$ , $0.6 R$ , and R. As shown in Fig. 3, the beacon node divides neighbor nodes into three groups of neighbor nodes A, B and C. In the group A, all the neighbor nodes can receive broadcast information from the beacon node when the communication radius is $0.3 R$ , and the minimum hop count is 0.3. In the group B, all the neighbor nodes can receive broadcast information from the beacon node when the communication radius is $0.6 R$ , and the minimum hop count is 0.6. In the group C, all the neighbor nodes can receive broadcast information from the beacon node when the communication radius is R, and the minimum hop count is 1.

Fig. 3.

Plot of neighbor nodes deployment.

After subdivision the minimum hop count between the beacon node and neighbor nodes, we use adaptive hop threshold mechanism to decrease the computation complexity: $\begin{matrix} (4) & V = ⌊ \frac{L_{D}}{R} ⌋ \end{matrix}$ where $L_{D}$ is the diagonal length of sensor nodes deployment area, R is the communication radius of sensor nodes, V is the value of adaptive hop threshold, $⌊ ⌋$ is a symbol for floor.

The threshold mechanism in this paper does not need the hop threshold pre-value, the adaptive value of the hop threshold changes with the change in WSN parameters, which not only decreases the computation complexity but also achieves the localization accuracy.

3.2. Improvement of the average hop distance

In order to solve the problem that the unknown node only uses the average hop distance from the nearest beacon node to calculate the estimated distance to the farthest beacon node and neglects the deployment situation of neighbor nodes of the farthest node in the Fig. 2, and reduces the calculation error of the average hop distance of the beacon node and the accumulative error of the estimated distance between the unknown node and the beacon node, our proposed algorithm improves the calculation method of the estimated distance between the unknown node and the beacon node, which is divided into two stages:

In general, the localization error obeys the Gauss distribution. On the basis of the parameter estimation theory, as the cost function of estimating sub-error, using the mean square error is more reasonable than using the variance or deviation [15]. So, we use the minimum mean square error criterion [12] to calculate the initial average hop distance of the beacon node: $\begin{matrix} (5) & f = \frac{1}{N_{A} - 1} \sum_{i \neq j} {(d_{i j} - d_{{Hop}_{i}} \times h_{i j})}^{2} \end{matrix}$ where $N_{A}$ is the number of beacon nodes, $d_{i j}$ is the real distance between the beacon node i and j, $h_{i j}$ is the minimum hop count between the beacon node i and j.

Set $\frac{\partial f}{\partial d_{{Hop}_{i}}} = 0$ , the initial average hop distance based on the minimum mean square error criterion can be obtained as follows: $\begin{matrix} (6) & d_{{Hop}_{i}} = \frac{\sum_{i \neq j} h_{i j} \times d_{i j}}{\sum_{i \neq j} h_{i j}^{2}} \end{matrix}$

After obtaining the initial average hop distance based on the minimum mean square error criterion, our proposed algorithm corrects the initial average hop distance error. In the DV-Hop algorithm, the estimated distance error will increases with the increase in the number of the minimum hop count. In this paper, the real distance between the beacon node i and the farthest beacon node k from the beacon node i is taken as an amendment reference to correct the error: $\begin{matrix} (7) & ε_{i} = \frac{\sqrt{{(x_{i} - x_{k})}^{2} + {(y_{i} - y_{k})}^{2}} - d_{{Hop}_{i}} \times h_{i k}}{h_{i k}} \end{matrix}$

The modified average hop distance of the beacon node is: $\begin{matrix} (8) & {HopSize}_{i} = d_{{Hop}_{i}} + ε_{i} \end{matrix}$

DV-Hop algorithm only uses the average hop distance of the nearest beacon node as the average hop distance of the unknown node to calculate the estimated distance, but in the actual networks, the average hop distance of one single beacon node can not fully reflect the attributes of all sensor nodes in the networks. Therefore, our proposed algorithm adopts the weighted average strategy, and the average hop distance of the unknown node is weighted by the average hop distance of each beacon node in the networks. The minimum hop count between the unknown and each beacon node is used as the weighted parameter of the average hop distance of the unknown node respectively, and all the weights are normalized: $\begin{matrix} (9) & λ_{k} = \frac{1 / (| h_{k} - h_{min} | + 1)}{\sum_{k = 1}^{N_{A}} 1 / (| h_{k} - h_{min} | + 1)} \end{matrix}$ where $h_{k}$ is the minimum hop count between the unknown node and the beacon node k, $h_{\min}$ is the minimum value of the minimum hop count between the unknown node and each beacon node.

After the unknown node receives the minimum hop count from all the beacon nodes and the modified hop distance of each beacon node, according to the principle that the error is bigger with the longer of the estimated distance, the beacon node is assigned smaller weight, which has the bigger value of the minimum hop count. On the basis of different weights in Eq. (9) and the modified average hop distances of all the beacon nodes in Eq. (8), the average hop distance of each unknown node is given by: $\begin{matrix} (10) & {HopSizeU}_{u} = \sum_{i = 1}^{N_{A}} λ_{i} \times {HopSize}_{i} \end{matrix}$ where ${HopSizeU}_{u}$ is the average hop distance of the unknown node u.

4. Simulation results and performance analysis

4.1. Localization in the random deployment environment of sensor nodes

In order to verify the localization performance of our proposed algorithm in the random deployment environment of sensor nodes, DV-Hop algorithm, the improved algorithm in Ref. [7], 2-DV-Hop(B) algorithm in Ref. [12], 3-DV-Hop(B) algorithm in Ref. [12] and our proposed algorithm have been simulated in Matlab2014a. The average localization error is defined by Eq. (11): $\begin{matrix} (11) & E = \frac{\sum_{i = 1}^{N_{U}} \sqrt{{(x_{i} - x_{i 1})}^{2} + {(y_{i} - y_{i 1})}^{2}}}{N_{U} \times R} \end{matrix}$ where $N_{U}$ is the total number of unknown nodes, R is the communication radius of sensor nodes, $(x_{i}, y_{i})$ are the actual coordinates of the unknown node and $(x_{i 1}, y_{i 1})$ are the estimated coordinates of the unknown node.

In the simulation environment, unknown nodes and beacon nodes are randomly deployed in a 2-D area of $100 m \times 100 m$ . The number of random deployment sensor nodes is 100, of which the number of beacon nodes is 5, 10, 15, 20, 25, 30, 35, 40 and 50 respectively. The communication radius is 20 m, 25 m, 30 m, 35 m, 40 m, 45 m and 50 m respectively. The value of ω is 5. To get better accuracy, each algorithm is run 100 times, and the experimental result of each algorithm is the average result of 100 running.

4.1.1. Effect on average localization error when varying communication radius

In the simulation, we compare the average localization error as the communication radius is changed. The total number of beacon nodes is 100, and the number of beacon nodes is 20. The communication radius varies from 20 m to 50 m. The results of the simulation are shown in Fig. 4.

Fig. 4.

Comparison of varying communication radii (random deployment of sensor nodes).

As shown in Fig. 4, with the increase of the communication radius, the average localization error of each algorithm is decreasing. The reason is that when the ratio of beacon nodes is constant, the networks connectivity increases with the increase in the communication radius, which reduces the average localization error of unknown nodes. In the process of increasing the communication radius from 20 m to 50 m, the average localization error of our proposed algorithm is less than the DV-Hop algorithm by 9.5%∼19%, less 6.5%∼9% than the improved algorithm in Ref. [7], less 5%∼6.5% than the 2-DV-Hop(B) algorithm in Ref. [12], and less 1%∼2% than the 3-DV-Hop(B) algorithm in Ref. [12]. This is because with the increase of the communication radius, the adaptive value for the number of communication radii of each beacon node based on Eq. (3) is also increased, which further subdivides the minimum hop count between the unknown node and each beacon node, and effectively improves the localization accuracy of the unknown node.

4.1.2. Effect on average localization error by varying the number of beacon nodes

In this experiment, the number of beacon nodes is changed and the localization performances of five algorithms are checked in terms of the average localization error. The communication radius is set to 30 m. The number of beacon nodes varies from 5 to 50. The results of the experiment are shown in Fig. 5. As seen from the Fig. 5, when the number of beacon nodes changes from 5 to 50, the average localization error of our proposed algorithm is the smallest, and the localization performance of our proposed algorithm is obviously better than DV-Hop algorithm. When the number of the beacon nodes is less than 10, the adaptive value for the number of communication radii in our proposed algorithm is 2, indicating that the beacon nodes use two communication radii to flooding broadcasting. The average localization error is reduced by 2.8%∼5.97% and 2.97%∼13.35% respectively compared with the improved algorithm in Ref. [7] and the 2-DV-Hop(B) algorithm in Ref. [12], which are both using two communication radii, and compared with the 3-DV-Hop(B) algorithm in Ref. [12] which uses three communication radii, the average localization error is also reduced by 1%∼8.35%. It shows that the optimization strategy of the average hop distance in our proposed algorithm makes the average hop distances of sensor nodes more accurate. When the number of beacon nodes is more than 10, the average localization error of our proposed algorithm is still the lowest and showing a downward trend.

Fig. 5.

Comparison of varying number of beacon nodes (random deployment of sensor nodes).

4.2. Localization in the nonrandom deployment environment of beacon nodes

In order to verify the localization performance in the nonrandom deployment environment of beacon nodes, we have simulated DV-Hop algorithm, 2-DV-Hop(C) algorithm in Ref. [12], 3-DV-Hop(C) algorithm in Ref. [12] and our proposed algorithm (the improved algorithm in Ref. [7] did not do nonrandom deployment experiments of beacon nodes in their paper) by Matlab2014a. The average localization error is used to compare the localization performances of four algorithms. The sensor nodes deployment area is a $100 m \times 100 m$ 2-D area. The number of sensor nodes is 100, of which the number of beacon node is 4, 9, 16, 25, 36 and 49 respectively. Beacon nodes are deployed by the nonrandom deployment method in Ref. [12], and the unknown nodes are deployed by the random deployment method. The node communication radius is 20 m, 25 m, 30 m, 35 m, 40 m, 45 m and 50 m respectively. The value of ω is 5. Each algorithm run 100 times in the simulation, and the average result of 100 running is taken as the experiment result.

4.2.1. Effect on average localization error when varying communication radius

In this experiment, we compare the average localization error of our proposed algorithm with three other algorithms by varying communication radius in the nonrandom deployment environment of beacon nodes. The communication radius varies from 20 m to 50 m and the number of beacon nodes is 25. The results of the experiment are shown in Fig. 6.

Fig. 6.

Comparison of varying communication radii (nonrandom deployment of beacon nodes).

Because of the nonrandom deployment environment of beacon nodes, the deployment of beacon nodes was more uniform, but when communication radius was small and the number of neighbor nodes was less, the accumulative error of the estimated distance increased and the average localization error was high. With the increase of communication radius, the number of neighbor nodes increased, and the accumulative error decreased, resulting in the reduction of the average localization error. As shown in Fig. 6, when the communication radius is increased from 20 m to 50 m, the average localization error of the DV-Hop algorithm is reduced from 48% to 28.1%, the average localization error of the 2-DV-Hop(C) algorithm in Ref. [12] is reduced from 29% to 15.3%, the average localization error of the 3-DV-Hop(C) algorithm in Ref. [12] is reduced from 24.5% to 10.3%, and the average localization error of our proposed algorithm is reduced from 21% to 7.2%. It shows that the localization performance of our proposed algorithm in the nonrandom deployment environment of beacon nodes is still better than the DV-Hop algorithm and two algorithms in Ref. [12].

4.2.2. Effect on average localization error by varying the number of nonrandom deployed beacon nodes

In this simulation, the average localization error comparison is made as the number of beacon nodes in the nonrandom deployment is changed. The communication radius is 30 m, the number of nonrandom deployed beacon nodes is 4, 9, 16, 25, 36 and 49 respectively. The results of the simulation are shown in Fig. 7.

Fig. 7.

Comparison of varying number of beacon nodes (nonrandom deployment of beacon nodes).

As shown in Fig. 7, when the number of beacon nodes is increased from 4 to 16, it can be seen that the average localization errors of four algorithms obviously decrease, indicating that the number of beacon nodes at this stage has a greater impact on the average localization error. When the number of beacon nodes is increased from 16 to 36, the average localization error of the DV-Hop algorithm is still worst, both the average localization error of 2-DV-Hop(C) algorithm in Ref. [12] and 3-DV-Hop(C) algorithm in Ref. [12] have a small fluctuation, and the average localization error curve of our proposed algorithm is at the bottom and the change is gentle. It shows that our proposed algorithm has the best localization accuracy and the robustness is better than the 2-DV-Hop(C) algorithm in Ref. [12] and 3-DV-Hop(C) algorithm in Ref. [12]. When the number of beacon nodes is more than 36, the average localization errors of four algorithms tend to be stable. It shows that the number of beacon nodes has little influence on the average localization error. The average localization error of the DV-Hop algorithm is close to 32.5%, the average localization error of the 2-DV-Hop(C) algorithm in Ref. [12] is close to 17%, the average localization error of the 3-DV-Hop(C) algorithm in Ref. [12] approaches to 15%, and the average localization error of our proposed algorithm approaches to 11%. The localization performance of our proposed algorithm is the highest.

4.3. Summary of simulation results

Table 1 summarizes the simulation results in the random deployment environment of sensor nodes and nonrandom deployment environment of beacon nodes.

Table 1
Summary of simulation results

Deployment environment Algorithm Communication radius (m) Number of beacon nodes Number of communication radii Average localization error (R)

Random DV-Hop 20∼50 5∼50 1 0.4794∼0.2672

Random Algorithm in Ref. [7] 20∼50 5∼50 2 0.4304∼0.1703

Random 2-DV-Hop(B) in Ref. [12] 20∼50 5∼50 2 0.4298∼0.1435

Random 3-DV-Hop(B) in Ref. [12] 20∼50 5∼50 3 0.3998∼0.0935

Random Proposed algorithm 20∼50 5∼50 2∼4 0.3962∼0.0835

Nonrandom DV-Hop 20∼50 4∼49 1 0.4800∼0.2810

Nonrandom 2-DV-Hop(C) in Ref. [12] 20∼50 4∼49 2 0.2900∼0.1530

Nonrandom 3-DV-Hop(C) in Ref. [12] 20∼50 4∼49 3 0.2450∼0.1030

Nonrandom Proposed algorithm 20∼50 4∼49 2∼4 0.2100∼0.0720

Deployment environment	Algorithm	Communication radius (m)	Number of beacon nodes	Number of communication radii	Average localization error (R)
Random	DV-Hop	20∼50	5∼50	1	0.4794∼0.2672
Random	Algorithm in Ref. [7]	20∼50	5∼50	2	0.4304∼0.1703
Random	2-DV-Hop(B) in Ref. [12]	20∼50	5∼50	2	0.4298∼0.1435
Random	3-DV-Hop(B) in Ref. [12]	20∼50	5∼50	3	0.3998∼0.0935
Random	Proposed algorithm	20∼50	5∼50	2∼4	0.3962∼0.0835
Nonrandom	DV-Hop	20∼50	4∼49	1	0.4800∼0.2810
Nonrandom	2-DV-Hop(C) in Ref. [12]	20∼50	4∼49	2	0.2900∼0.1530
Nonrandom	3-DV-Hop(C) in Ref. [12]	20∼50	4∼49	3	0.2450∼0.1030
Nonrandom	Proposed algorithm	20∼50	4∼49	2∼4	0.2100∼0.0720

From Table 1, we can make the following comments about our proposed algorithm:

In both environments where sensor nodes random deployment and beacon nodes nonrandom deployment, with the increase of the communication radius and the number of beacon nodes, the number of communication radii in DV-Hop algorithm, the improved algorithm in Ref. [7] and four algorithms in Ref. [12] are fixed, but the number of communication radii in our proposed algorithm increases from 2 to 4. Therefore, compared with DV-Hop algorithm, the improved algorithm in Ref. [7] and four algorithms in Ref. [12], our proposed algorithm has the advantage of adaptive selection of number of communication radii.

In our proposed algorithm, the proposed methods can successfully uses for all cases when there are two different deployment environment, since our proposed algorithm has the lowest average localization error, compared with DV-Hop algorithm, the improved algorithm in Ref. [7] and four algorithms in Ref. [12]. Thus, our proposed algorithm has better localization performance, environmental adaptability and robustness.

5. Conclusions

In view of the defects of the DV-Hop algorithm in random deployment network environment, the reasons for the average localization error of the DV-Hop algorithm are analyzed, and we have proposed an improved DV-Hop algorithm based on adaptive hop count and the average hop distance optimization. The proposed algorithm improve the DV-Hop algorithm from three aspects: the subdivision of the minimum hop count of sensor nodes, the correction of the average hop distance of beacon nodes and the optimization of the average hop distance of unknown nodes. The localization performance of five algorithms have been simulated and have compared in the random deployment environment of sensor nodes with different communication radius and number of beacon nodes, and the comparison experiments have been carried out on the localization performance of four algorithms in the nonrandom deployment environment of beacon nodes with different communication radius and number of beacon nodes. The simulation results show that our proposed algorithm is obviously better than the DV-Hop algorithm in the localization performance, and it also has a certain improvement compared with the comparative literatures, which prove that the improved strategy of our proposed algorithm can effectively improve the localization accuracy of the DV-Hop algorithm. In the future, how to make the estimated distance of unknown nodes closer to the real distance will be the key work that needs further analysis and research.

References

Chen,

Y.L.

Chu and

M.T.

Sun, Neighbor-based hop size estimation for dense sensor networks, Journal of Information Science & Engineering 31 (2015), 879–896.

Cheng and

L.Y.

Xia, An effective cuckoo search algorithm for node localization in wireless sensor network, Sensors 16 (2016), 1390. doi:10.3390/s16091390.

Z.H.

Cui,

Sun,

G.G.

Wang,

Xue and

J.J.

Chen, A novel oriented cuckoo search algorithm to improve DV-Hop performance for cyber-physical systems, Journal of Parallel & Distributed Computing 103 (2016), 42–52. doi:10.1016/j.jpdc.2016.10.011.

Halder and

Ghosal, A survey on mobile anchor assisted localization techniques in wireless sensor networks, Wireless Networks 60 (2015), 1–20.

Y.H.

Huang,

R.W.

Zhao and

X.R.

Chen, An anchor-free localization algorithm with phase advantages, Acta Electronica Sinica 43 (2015), 2536–2541.

Kaur,

Kumar and

G.P.

Gupta, A weighted centroid localization algorithm for randomly deployed wireless sensor networks, Journal of King Saud University – Computer and Information Sciences (2017). doi:10.1016/j.jksuci.2017.01.007.

Li,

Liu,

Z.H.

Qian and

C.G.

Lu, Improved DV-Hop localization algorithm based on two communication ranges for wireless sensor network, Journal of Jilin University Engineering and Technology Edition 44 (2014), 502–507.

C.G.

Liu,

S.L.

Liu,

W.B.

Zhang and

D.L.

Zhao, The performance evaluation of hybrid localization algorithm in wireless sensor networks, Mobile Networks & Applications 21 (2016), 994–1001. doi:10.1007/s11036-016-0737-1.

D.F.

Liu,

Zhang,

X.Y.

Bing,

Y.Q.

Shao and

B.G.

Xu, Localization method based on modified cuckoo difference optimization for wireless sensor networks, Journal of System Simulation 29 (2017), 791–797.

10.

J.L.

Liu,

Wang,

M.W.

Yao and

Z.L.

Qiu, VN-APIT: Virtual nodes-based range-free APIT localization scheme for WSN, Wireless Networks 22 (2016), 867–878. doi:10.1007/s11276-015-1007-z.

11.

W.Y.

Liu,

E.S.

Wang,

Z.J.

Chen and

Wang, An improved DV-Hop localization algorithm based on the selection of beacon nodes, Journal of Convergence Information Technology 5 (2010), 157–164.

12.

S.L.

Ma and

J.P.

Zhao, Multi communication ranges DVHop localization algorithm for wireless sensor network, Chinese Journal of Sensors and Actuators 29 (2016), 593–600. doi:10.1016/j.snb.2015.11.083.

13.

Shi,

Y.P.

Li,

Gao,

Bai and

S.J.

Xie, Twice-refinement DV-HOP localization algorithm based on membership, Chinese Journal of Scientific Instrument 33 (2012), 2615–2621.

14.

Tomic and

Mezei, Improvements of DV-Hop localization algorithm for wireless sensor networks, Telecommunication Systems 61 (2016), 93–106. doi:10.1007/s11235-015-0014-9.

15.

M.T.

Xiang,

Wang and

Y.H.

Yang, An improved DV-Hop localization algorithm based on threshold mechanism and correcting distance for wireless sensor networks, Chinese Journal of Sensors and Actuators 29 (2016), 920–926.

16.

Xiong,

Z.Y.

Chen,

An and

B.Y.

Yang, Robust TDOA localization algorithm for asynchronous wireless sensor networks, International Journal of Distributed Sensor Networks 2015 (2015).

17.

D.G.

Zhang,

H.L.

Niu,

Liu and

X.C.

Ming, Novel positioning service computing method for WSN, Wireless Personal Communications 92 (2017), 1747–1769. doi:10.1007/s11277-016-3632-y.