Frontiers in Computing and Intelligent Systems 
ISSN: 2832-6024 | Vol. 2, No. 1, 2022 

 

42 

Application of Improved DV-Hop algorithm in Wireless 
Sensor Network 

Jiaowu Cai1, Liangyu Li1, Zhijun Zhang2 

1 College of Information Engineering Zhongshan Polytechnic, Zhongshan 528400, China 
2 Jiangxi Coal Industry Group Co., Ltd, Pingxiang 337000, China 

 

Abstract: To improve the problem of inaccurate wireless sensor network positioning algorithm of DV-Hop node is proposed. 

Firstly, the optimization scheme of the anchor nodes is completed by calculating the triangle area of the anchor nodes. 

Furthermore, the particle group optimization algorithm combines the genetic chaotic particle group theory, and finally, the 

improved particle group algorithm is used to correct the node position obtained by the DV-Hop algorithm. The simulation 

experiments show that improving the DV-Hop algorithm compared with the traditional D V-Hop algorithm to monitor the 

underground leakage accident position more accurately. 

Keywords: Particle swarm algorithm; Genetic algorithm; DV-Hop; Wireless sensor network. 

 

1. Introduction 

With the development of wireless communication 

technology, wireless sensor network (WSN) is increasingly 

used in coal mines.among DV-Hop[1-2]As a no-need ranging 

and positioning algorithm, it is very suitable for WSN node 

positioning under the mine. Many optimization algorithms 

have been improved to reduce localization error and improve 

localization accuracy [3-7]. document [3] The ant colony 

particle swarm algorithm is introduced into the unknown node 

computation stage of the DV-Hop algorithm to improve the 

localization accuracy. Document [4] The problem of collinear 

anchor nodes is removed by using the angle comparison 

principle of the multilateral measurement method. Document 

[5] The frog algorithm is introduced to solve the average per 

hop distance, thus reducing the node localization error and 

making it closer to the actual value. These algorithms 

contribute to some extent to optimize the performance of the 

DV-Hop algorithm, but they still have shortcomings. Based 

on the DV-Hop positioning algorithm, an anchor node 

optimization method avoids the problem that the nodes cannot 

be located, and proposes a DV-Hop improvement scheme 

based on the genetic chaotic particle swarm algorithm to 

reduce the average positioning error of downhole distribution 

network faults and improve the positioning accuracy. 

2. Analysis and improvement of the 
DV-Hop algorithm 

2.1. DV-Hop algorithm 

The DV-Hop algorithm process is located as follows: 

Step 1 anchor node will its own information (ID, 

coordinates, anchor receiving information node jump) 

through the flood, the initial value of jump is set to 0, each 

critical point received the information and update the 

minimum jump, and jump number plus 1, and continue to 

forward to the neighbor node, this rule to obtain the unknown 

node from each anchor node minimum jump value. 

 Step 2 takes the jumps of other anchor nodes and the 

average distance per jump of the anchor node is calculated 

according to Eq. (1). 

𝑑𝑖𝑠𝑎 =
∑ √(𝑥𝑖−𝑥𝑗)2+(𝑦𝑖−𝑦𝑗)2

𝑖≠𝑗

∑ ℎ𝑐𝑖𝑗𝑖≠𝑗

           (1) 

In this Eq.: (𝑥𝑖 , 𝑦𝑖)  and (𝑥𝑗 , 𝑦𝑗)  are the coordinates of 

anchor nodes 𝑖 and𝑗 .ℎ𝑐𝑖𝑗 is the minimum number of jumps 

between anchor node 𝑖 and node𝑗. 

Step 3: Using the three-sided measurement method, the 

distance between the unknown node A0 and the anchor nodes 

A1, A2, and A3, as shown in Figure 1, is calculated by Eq.(2). 

{

√(𝑥1 − 𝑥)2 + (𝑦1 − 𝑦)2 = 𝑑1

√(𝑥2 − 𝑥)2 + (𝑦2 − 𝑦)2 = 𝑑2

√(𝑥3 − 𝑥)2 + (𝑦3 − 𝑦)2 = 𝑑3

         (2) 

 
Figure 1. Schematic diagram of the trilateral measurement method 

Convert Eq. (2) to the format of Eq. AX =P: 



















−−

−−

−−

=

−− )()(

)()(

)()(

11

22

11

kkkk

kk

kk

yyxx

yyxx

yyxx

A


         (3) 

𝑋 = [
𝑥
𝑦]                        4) 





















−+−+−

−+−+−

−+−+−

=

−−=

2

1

222

1

22

1

2

2

222

2

22

2

2

1

222

1

22

1

2

1

kkkkkk

kkk

kkk

ddyyxx

ddyyxx

ddyyxx

P


    (5) 



 

43 

Using least squares estimation: 

𝑋 = (𝐴𝑇𝐴)−1𝐴𝑇𝑃               (6) 

2.2. Deficiency of the D V-Hop algorithm 

(1) The topological relationship of anchor nodes will 

directly affect the positioning accuracy of wireless sensor 

nodes. Figure 2 shows the distribution of wireless sensor 

nodes in the underground coal mine power grid [8]. Due to 

the long and narrow geographical environment of the 

underground coal mine, the sensors in the distribution 

network cannot meet the requirements of uniform layout 

during installation, which will produce the sensor node 

collinear or approximate collinear situation, neither of which 

can achieve the node positioning. Therefore, the removal of 

collinearity and the selection of suitable anchor nodes 

becomes a key problem. 

 
Figure 2. Distribution diagram of wireless sensors in underground 

coal mine power grid 

In the DV-Hop algorithm, the average distance often errors 

with the actual value due to the influence of environment and 

communication. And once the error occurs, it will be 

cumulative to affect the subsequent calculation, and 

eventually lead to greater calculation errors. Therefore, the 

calculation error must be reduced by correcting for the 

unknown node coordinates. 

3. Improvement of the DV-Hop 
algorithm 

3.1. Anchor node preferred scheme 

In this paper, the area of anchor node by calculating 

whether the anchor node is collinear:𝑆𝑛 

𝑆𝑛 = |

𝑥𝑖 𝑦𝑖 1
𝑥𝑗 𝑦𝑗 1

𝑥𝑘 𝑦𝑘 1
|                (7) 

Assume that (𝑥𝑖 , 𝑦𝑖) , (𝑥𝑗 , 𝑦𝑗)  and (𝑥𝑘 , 𝑦𝑘)  are the 

coordinates of 3 anchor nodes randomly distributed,𝑆𝑛is the 

triangle area composed of anchor nodes.If 0 ≤ 𝑆𝑛 ≤ 𝛿, then 

these three anchor nodes are considered to be in an 

approximate line, so another anchor nodes are needed to assist 

in positioning. 

3.2. Particle swarm optimization DV-Hop 

The particle swarm optimization algorithm PSO (Particle 

Swarm Optimization) shows its unique advantages in 

handling optimization problems due to its excellent global 

search performance and fast convergence ability [9]. PSO 

starts from the random solution, for the 𝑛  -dimensional 

optimization problem, randomly generates the initial 

population of 𝑚 particles, and substitutes the flight speed 𝑉𝑖 

and position 𝑋𝑖  of the 𝑖 th particle into the optimization 

objective function to obtain the fitness value. After updating 

𝑉𝑖 and location 𝑋𝑖 and iteration, the optimal solution is found. 

The optimal solution obtained by the 𝑖 th particle search is 

recorded as 𝑝𝑖 , and the current optimal solution obtained by 

particle swarm search is recorded as 𝑝𝑏 , and 𝑉𝑖 and 𝑋𝑖 are 

updated by using Eq. (8) and Eq. (9).  

𝑋𝑖𝑛(𝑘 + 1) = 𝑋𝑖𝑛(𝑘) + 𝑉𝑖𝑛(𝑘 + 1)            (8) 

𝑉𝑖𝑛(𝑘 + 1) = 𝜔𝑉𝑖𝑛(𝑘) + 𝑐1𝑟1(𝑃𝑖𝑛 − 𝑋𝑖𝑛(𝑘)) +
𝑐2𝑟2(𝑃𝑏𝑛 − 𝑋𝑖𝑛(𝑘))               (9) 

In the equation, 𝑐1 and 𝑐2 are shrinkage factors, and 𝜔 is 

inertia weight. 

3.3. Genetic chaos particle swarm algorithm 

This paper presents a genetic chaos particle swarm 

algorithm called GCPSO (Genetic Chaos Particle Swarm 

Optimization) by introducing the chaos principle and the 

dynamic weight adaptive regulation method. 

3.3.1. Genetic algorithm 

The genetic algorithm GA (Genetic Algorithm) is a 

development law that simulates the continuous evolution of 

living organisms in nature [10]. In this paper, a new 

generation of elites is formed by introducing the crossover 

and variation of GA algorithm in the PSO algorithm, and 

finally the optimal solution of the optimization problem is 

obtained. 

(1) Select the crossover 

Select 𝑁  even individuals, then pair the selected 

individuals in pairs, perform cross operation, and generate 

offspring particles. Suppose that particle 𝑎  and particle 𝑏 

are selected for cross operation, and the corresponding 

positions 𝑋𝑎(𝑡)  and 𝑋𝑏(𝑡)  are replaced by the following 

descendants: 

𝑋1
𝑘 = 𝑟𝑋1

𝑘 + (1 − 𝑟)𝑋2
𝑘              (10) 

𝑋2
𝑘 = 𝑟𝑋2

𝑘 + (1 − 𝑟)𝑋2
𝑘            (11) 

Corresponding speed: 

𝑉1
𝑘 = 𝑟𝑉1

𝑘 + (1 − 𝑟)𝑉2
𝑘              (12) 

𝑉2
𝑘 = 𝑟𝑉2

𝑘 + (1 − 𝑟)𝑉1
𝑘             (13) 

2) Variant operation 

After crossing particles with probability 𝑃 , perform the 

following mutation operations: 

𝑥𝑖
𝑘+1 = {

𝑥𝑖
𝑘 + 𝑐𝑖 𝑖𝑓 𝑓𝑖𝑡𝑛𝑒𝑠𝑠(𝑥𝑖

𝑘 + 𝑐𝑖) > 𝑓𝑖𝑡𝑛𝑒𝑠𝑠(𝑥𝑖
𝑘)

𝑥𝑖
𝑘 𝑜𝑡ℎ𝑒𝑟𝑠

  14) 

𝑉𝑖
𝑘+1 = 𝑉𝑖

𝑘                      (15) 

In the equation, 𝑐𝑖  is the interval [𝑥𝐿 − 𝑥𝑖
𝑘, 𝑥𝑈 − 𝑥𝑖

𝑘] 

uniformly distributed random number, 𝑥𝐿  and 𝑥𝑈  are the 

upper and lower limits of search respectively. 

3.3.2. Adaptive parameter adjustment 

Chaos is a nonlinear motion which is very sensitive to 

initial conditions and can traverse all states. In this paper, the 

chaos principle is used to optimize the velocity 𝑉𝑖  and 

position 𝑋𝑖  of particles by adaptively adjusting the 

parameters of particle swarm optimization algorithm. Create 

a chaotic sequence as follows: 

𝛽𝑘+1 = 𝜆𝛽𝑘(1 − 𝛽𝑘)               (16) 

When 𝜆 = 4, the system will enter into a chaotic state, 

and the chaotic variable 𝛽𝑡(𝑡 = 1,2, ⋯ )  will traverse all 

the states in the system without repetition. After that, 𝑟1 and 



 

44 

𝑟2  are dynamically adjusted to generate an excellent 

population, and then lead the particles to the optimal solution 

through equations (8) and (9). Chaotic optimization is as 

follows: 

{
𝑟𝑖

𝑘+1 = 4.0 × 𝑟𝑖
𝑘(1 − 𝑟𝑖)

𝑟𝑖
𝑘 ∈ (0,1), 𝑖 = 1,2

            (17) 

Inertial weights 𝜔 play a role in maintaining algorithmic 

balance in optimization. This paper chooses the dynamic 

weight adjustment method, and the weight update Eq. is: 

𝜔(𝑘) = 𝜔𝑚𝑎𝑥 −
(𝜔𝑚𝑎𝑥 −𝜔𝑚𝑖𝑛 )×𝑘

𝑘𝑚𝑎𝑥
        (18) 

In the equation, 𝜔𝑚𝑎𝑥   and 𝜔𝑚𝑖𝑛   are the upper and 

lower limits of inertia weight; 𝑘  is the current iteration 

number; 𝑘𝑚𝑎𝑥  is the maximum number of iterations. 

3.4. DV-Hop improvement based on genetic 

chaos particles 

DV-Hop algorithm (GCPSO-Hop) and DV-Hop algorithm 

based on genetic chaos particle swarm algorithm have the 

same communication energy consumption, but GCPSO-Hop 

algorithm has slightly more computing energy consumption 

than DV-Hop algorithm. Since the energy consumption of the 

wireless sensor network is mainly generated by the 

communication energy consumption, so the energy 

consumption of the GCPSO-Hop positioning algorithm meets 

the application conditions. This paper targets 𝑓𝑖  as the 

minimum localization error: 

𝑓𝑖 = ∑ 𝑑𝑘 − √(𝑥 − 𝑥𝑖)
2 + (𝑦 − 𝑦𝑖)2𝑛

𝑖=1     (19) 

In the equation, (𝑥, 𝑦)  is the coordinate of the unknown 

node, (𝑥𝑖 , 𝑦𝑖) is the coordinate of the anchor node, and 𝑑𝑘 is 

the actual measured distance. The fitness function is: The 

fitness function is: 

𝑓𝑖𝑡𝑛𝑒𝑠𝑠(𝑥) = ∑ 𝛼𝑖𝑓𝑖(𝑥, 𝑦)𝑛
𝑖=1           (20) 

 In the equation, 𝛼𝑖A is the inverse ratio of the number of 

hops of unknown node and anchor node 𝑖; 𝑛 is the number 

of unknown nodes. In this paper, we use the GCPSO 

algorithm to correct the coordinates of unknown nodes found 

in the later part of the DV-Hop algorithm. The specific 

optimization steps are as follows: 

Step 1 The average hop distance 𝑑𝑖𝑠𝑎  and the minimum 

hop number ℎ𝑐𝑖𝑗 are obtained through step 1 and Step 2 of 

the DV Hop algorithm. 

Step 2 Initialize particle swarm. Initialize particle velocity 

𝑉𝑖 and position 𝑋𝑖, and set the number of iterations 𝑘 = 0. 

Step 3 Calculate the fitness value 𝑓𝑖𝑡𝑛𝑒𝑠𝑠  according to 

equation (20). 

Step 4 Compare the fitness of each particle. The individual 

optimal solution in the group is set as 𝑃𝑖  , and the global 

optimal solution is set as 𝑃𝑏 . 

Step 5 Update the velocity 𝑉𝑖 and position 𝑋𝑖 of particles 

according to Formula (8) and Formula (9). 

Step 6 Determine whether the algorithm is terminated. If 

the maximum number of iterations is reached, the optimal 

solution will be output; otherwise, go to Step 7. 

Step 7 Randomly select 𝑀  individuals according to the 

fitness value, and perform cross operation on them to obtain 

𝑀 new individuals. 

Step 8 Perform mutation operation on all individuals, 

select 𝑁  individuals with high fitness from 𝑀 + 𝑁  to 

enter the next generation, and return to Step 3. 

4. Experimental Simulation and 
Results analysis 

To verify the effectiveness of the improved algorithm, 

sensor nodes are randomly generated in a simulation region 

of 100 m×100 m. Simulation experiments using MATLAB for 

GCPSO-Hop, DV-Hop, GA-Hop and Posho, and analyze the 

results were analyzed. The absolute positioning error is: 

𝑒 = √(𝑥 − 𝑥𝑒)2 + (𝑦 − 𝑦𝑒)2           (21) 

Relative definition error is: 

�̂�𝑒𝑟𝑟 =
∑ 𝑒𝑒𝑟𝑟

𝑛
1

𝑅
                 (22) 

 In the equation, (𝑥, 𝑦)  is the actual coordinate of the 

unknown node, (𝑥𝑒 , 𝑦𝑒)  is the estimated coordinate, and 𝑅 

is the communication radius. Set 𝑐1 = 𝑐2 = 2.0 , 𝜔𝑚𝑎𝑥 =
0.9, 𝜔𝑚𝑖𝑛 = 0.4, genetic crossover probability 𝑃 = 0.85, 

population size of each generation 𝑁 = 40 , and iteration 

number 𝑘 = 200. 

communication radius. Setting, genetic crossing 

probabilities, size of the population per generation, number of 

iterations. 

Because the coal mine underground roadway is narrow and 

slender and the open space is limited. In order to reduce the 

error of the node communication, reducing the distance 

between the deployment paving nodes and adding the 

redundant nodes is adopted to ensure the communication 

between the nodes. In addition, a denser single-chain 

deployment mode is adopted in the narrow width lanes to 

ensure the communication quality between nodes. In order to 

test the performance of this algorithm, the experimental 

platform of simulated ZigBee wireless sensor distribution 

network is built. A schematic diagram of the experimental 

platform is shown in Figure 3. The power supply is a three-

phase current source, the single-phase output current is 1 

A~100 A, the isolation transformer ratio is 1:1, R is the 

protection resistance, A, B and C are three-phase upper 

current sensors. Once the circuit in the grid ground fault, the 

three-phase line loses balance will appear zero order 

component. After the signal adjustment circuit, the 0~3.3V 

voltage signal is output, and then converted into a digital 

signal by the A / D converter, and ultimately conducive to the 

ZigBee wireless technology transmission to the terminal. 

Table 1 shows the zero-order current of the measured 

alignment lines. 

 
Figure 3. Schematic diagram of the experimental platform 

structure 

Figure 4 is a random distribution plot of the nodes. The 

asterisk is the unknown node, and the cross symbol is the 

anchor node. At this time, the anchor node is approximately 

collinear with the underground coal mine. Figure 5 shows the 



 

45 

localization effect of undetecting collinearity and excluding 

colollinearity. As shown in Figure 5 (a) and Figure 5 (b), the 

localization effect after excluding collinearity scheme is 

better, which can effectively reduce the average localization 

error of nodes. 

Table 1. Zero-order current error of transmission line measured by 
wireless sensor network 

Order 

number 

Line zero-

order 

current / A 

WSN detects zero-order 

current / A 
Error 

/% 

1 1.00 1.03 3.00 

2 3.00 3.14 4.67 

3 5.00 5.24 4.80 

4 7.00 7.36 5.14 

5 9.00 9.58 6.44 

6 11.00 10.46 4.91 

7 13.00 13.46 3.54 

8 15.00 15.63 4.20 

9 17.00 16.60 2.35 

10 19.00 18.71 1.53 

11 20.00 20.85 4.25 

average 

error 
- - 4.08 

 

 
Figure 4. Random distribution of the nodes 

 

 
Figure 5. excluded the localization mean error comparison before 

and after being approximately collinear 

Figure 6 shows the change curve of the average total 

number of anchor nodes between 5% and 35%. It can be seen 

from the figure that the average localization error of the four 

localization algorithms is constantly decreasing as the 

proportion of anchor nodes increases, and the localization 

performance of the GCPSO-Hop algorithm shows obvious 

advantages. At the anchor node ratio of 35%, the GCPSO-

Hop algorithm has the smallest average localization error and 

was 11.16% lower than DV-Hop. It show that GCPSO-Hop 

algorithm can improve node localization accuracy and reduce 

localization error. 

Figure 7 shows the relationship of the average localization 

error with the number of nodes with the same proportion of 

anchor nodes. As the number of nodes increases, the average 

localization error all decreases and gradually stabilizes. The 

average localization error of both the GA-Hop algorithm and 

the PSO-Hop algorithm was smaller than that of the DV-Hop 

algorithm, but it did not reach the optimization. Since the 

GCPSO-Hop algorithm is more accurate on the location 

correction obtained from the localization, the average 

localization error is smaller. 

 

 
Figure 6. The average localization error changes with the 

proportion of the anchor nodes 

 

 
Figure 7. Changes of the average localization error with the 

number of nodes 

 

 
Figure 8. Average localization error along with the node 

communication radius relationship 

For a more comprehensive analysis of the performance of 

the GAPSO-Hop algorithm. Figure 8 shows the average 

localization error change curve of the nodes at different 

communication radii when the anchor node ratio is 20%. It 

can be seen from the simulation results that when R hours as 

the communication radius increases, the average localization 

error begins to decrease. 

For example, at R = 10 m, the average localization error of 

the nodes of the GCPSO-Hop algorithm was reduced by 23.8% 

compared with that of the DV-Hop algorithm. When R is 

greater than 35m, although the connectivity change of the 

network increases the localization error as the communication 

radius increases. But then the GAPSO-Hop algorithm is still 



 

46 

the best of all the algorithms. To verify the effectiveness and 

accuracy of the GCPSO-Hop algorithm, six positioning nodes 

were selected in the underground coal mine for the validation 

experiment, and the experimental data are shown in Table 2. 

In Table 2, the actual coordinates of nodes are (𝑥, 𝑦) and the 

measured coordinates are (𝑥𝑒 , 𝑦𝑒) . From the actual 

measurement results, we can see that the GCPSO-Hop 

algorithm is closer to the actual value than other algorithms, 

and thus has smaller localization error and higher accuracy. 

Table 2. Actual measurement results 

 

5. Conclusion 

An improved DV-Hop algorithm is proposed for the 

identification of underground leakage accidents. Firstly, 

through the anchor node optimization scheme, the defect of 

the anchor node combination is avoided. On the basis of the 

particle swarm optimization algorithm, a genetic chaotic 

particle swarm optimization algorithm (GCPSO) is proposed 

to correct the estimated position of DV-Hop. Experimental 

simulations show that GCPSO-Hop algorithm has a better 

optimization effect than DV-Hop algorithm in reducing the 

average positioning error and improving the positioning 

accuracy, which proves the feasibility and effectiveness of 

GCPSO-Hop algorithm in the underground safety supervision 

process in coal mines. 

Acknowledgements 

The scientific research project "Intelligent Clothes Dryer 

Based on Wireless Sensor Network" of Zhongshan 

Polytechnic in 2022 (Project No.: KYB2204). 

References 

[1] Debessu Y G，Wu H C .Modified Turbo Decoder for Location 
in Single-Frequency Networks[C]/ /IEEE International 
Symposium on BMSB，2012:1-5. 

[2] stone, Jia Chuanjiang, Liang Huanhuan.improved wireless 
sensor network DV-Hop positioning algorithm [J] Journal of 
Sensing Technology, 2011,24 (1): 83-87. 

[3] Ye Rong, Zhao Lingkai. Wireless Sensor Network Positioning 
algorithm based on ant colony particle mixture [J]. Computer 
Measurement and Control, 2011,19 (3): 732-735. 

[4] Li Yahong, Feng Donghua. Location algorithm based on the 
Internet of Things [J]. Computer measurement and control, 
2012,20 (11): 2916-2918. 

[5] Ge Yu, Wang Xueping, Liang Jing. DV-Hop localization 
improvement based on frog algorithm [J]. Computer 
Applications, 2011,31 (4): 922-925. 

[6] Yi T T，Fang Z Y，Li Ｒ X .ＲMADV-HOP :An Improved 
DV-Hop Localization Algorithm[C]/ /Proceedings of the 2010 
Seventh International Conference on Information 
Technology :New Generation ， Las Vegas ， Nevada ，
2010:939-943. 

[7] Jiang Yusheng, Feng Yanhe. A new DV-Hop localization 
algorithm [J]. Journal of Sensing Technology, 2010,23 (12): 
1815-1819. 

[8] Wang Chaonan, Ding Enjie, Zhou Qiang, et al. Application of 
wireless sensor network [J]. Journal of Computer-Aided 
Design and Graphics, 2007,19 (3): 392-397. 

[9] Chen Xingzhou, Liao Minghong, Lin Jianhua. Improvement of 
node localization of wireless sensor network based on particle 
swarm optimization [J]. Computer Application, 2010,30 (7): 
1736-1738. 

[10] Side exuberant, Zeng Jing. Research on non-ranging node 
localization algorithm based onquantum genetic algorithm [J]. 
Computer Application and Software, 2013,30 (2): 180-183.