# A New Distance Vector-Hop Localization Algorithm Based on Half-Measure Weighted Centroid

Authors: Lu Jian Yin
Journal: Mobile Information Systems
 (2019)

---

## Abstract

Considering the defects of the Distance Vector-Hop (DV-Hop) localization algorithm making errors and having error accumulation in wireless sensor network (WSN), we proposed a new DV-Hop localization algorithm based on half-measure weighted centroid. This algorithm followed the two-dimensional position distribution, designed the minimum communication radius, and formed a reasonable network connectivity firstly. Then, the algorithm corrected the distance between the beacon node and its neighbour node to form a more accurate jump distance so that the shortest path can be optimized. Finally, we theorized the proposed localization algorithm and verified it in simulation experiments, including same communication radius, different communication radii, and different node densities in same communication radius, and have compared the localization error and localization accuracy, respectively, between the proposed algorithm and the DV-Hop localization algorithm. The experiment’s result shows that the proposed localization algorithm have reduced the localization’s average error and improved the localization’s accuracy.


---

## Body

## 1. Introduction

As there is rapid development in wireless communication, the rapid development of low energy, low cost, intensive, multifunctional tiny wireless sensor network is promoted. And a large number of wireless sensor nodes are one of the key elements of wireless sensor networks [1, 2]; therefore, research on location technology in wireless sensor networks is one of the key issues in the research of wireless sensor networks, which is of great significance.The DV-Hop localization algorithm [3] was first proposed by Dragos Niculescu et al. of Rutgers, USA, which is a distributed localization algorithm based on distance vector routing protocol without ranging [4]. Many scholars and scientific research institutions have carried out in-depth research on the DV-Hop Localization algorithm. In reference [5], in order to reduce the DV-Hop error, the ideal beacon node spacing is introduced to eliminate the larger error in the average single-hop distance calculated by the beacon node, and the average single-hop distance of the whole network is corrected. Then, the unknown node coordinates calculated by the least squares method are corrected. In reference [6], the weighted average of distance error and estimation distance error is proposed to correct the original average hop distance. The weight of the particle group is improved by using the subsection index and logarithmic decrement weight. In reference [7], for each beacon node, the weight of each beacon node is added to calculate the average hop distance. The main node definition is proposed, the network topology structure will be considered more comprehensively, and the local and global characteristics will be weighed better; in order to calculate the estimated distance of nodes, the improved particle swarm optimization algorithm is used instead of the maximum likelihood estimation method to locate the node coordinates. In reference [3], the range of broadcasting information of beacon nodes is limited by the threshold of the hop number; the average distance of each anchor node is corrected by the average distance error of each beacon node; the unknown node of this round is upgraded to a new anchor node for the next round of positioning. In reference [8], the multicommunication radius method is introduced to refine the hops between nodes. When calculating the average hop distance of unknown nodes, the isolated nodes are eliminated, and the average hop distance obtained by beacon nodes is weighted and normalized to improve the localization accuracy of unknown nodes. In reference [9], the distance between the unknown nodes and the beacon nodes is calculated using different average hop distances. Using the Galactic Swarm Optimization thought of beacon nodes in the network is divided into different species: the particle swarm optimization algorithm is used to estimate the unknown node in each population, which is the optimal location, and the weighted centroid algorithm is used to optimize the suboptimal solution which is set as the coordinates of the unknown node.All of the above studies give a good research idea for the DV-Hop localization algorithm. This paper proposes another improvement scheme based on the DV-Hop algorithm. This algorithm followed the two-dimensional position distribution, designed the minimum communication radius, and formed a reasonable network connectivity firstly. Then, the algorithm corrected the distance between the beacon node and its neighbour node to form a more accurate jump distance so that the shortest path can be optimized. Finally, we theorized the proposed localization algorithm and verified it in simulation experiments, including same communication radius, different communication radii, and different node density with same communication radius, and have compared the localization error and localization accuracy, respectively, between the proposed algorithm and the DV-Hop localization algorithm. The experimental result shows that the proposed localization algorithm have reduced the localization’s average error and improved the localization’s accuracy. Compared with the DV-Hop algorithm, whose localization accuracy increases from 0.6 to 0.7, other DV-HOP is about 0.3; and new DV-Hop shows a localization accuracy fluctuating stably within 0.1.


## 2. Analysis of the DV-Hop Localization Algorithm

The DV-Hop localization algorithm is a distributed range-free localization algorithm based on the distance vector routing protocol [5]. The main principle therein is to calculate the distances between beacon nodes and unknown nodes by multiplying the average hop distance in WSNs by the hop count of the beacon nodes. Then, the position information of unknown nodes is obtained through trilateration, triangulation, and multilateration [10], thus realizing localization. For a network topology established by a random arrangement of wireless sensor nodes, the 40 paths from beacon nodes to unknown nodes are possibly not straight. Hence, some errors are likely to exist in the node localization process when using the DV-Hop algorithm [11]. Moreover, the more numerous the hop counts, the larger the errors (i.e., error accumulation occurs).


### 2.1. Basic Procedure of the DV-Hop Algorithm

The localization of nodes using the DV-Hop [12, 13] algorithm is mainly divided into three steps.Step 1.
Calculating the minimum hop count between beacon nodes and unknown nodes. Beacon nodes broadcast information which shows their positions to neighbouring nodes by using the classical distance vector routing protocol [14]. The information contains id,xi,yi,Hi, where id, xi,yi, and Hi represent the identifier, the coordinate, and the hop count of beacon nodes i, respectively. Moreover, the initial value of Hi is set to zero. The nodes receiving the broadcast information record the localization and hop counts of beacon nodes as vectors, which are then transmitted to neighbouring nodes (the value of hop count is incremented by one). When a node receives the same id group, it is supposed to compare the newly obtained value of Hi with the original value and then select the minimum value to replace and update the original group; otherwise, the newly obtained group is abandoned. The position information and minimum hop count of all beacon nodes are obtained by this communication mode in WSNs.Step 2.
Estimating the average hop distance. The purpose of calculating the average hop distance and minimum hop count first is to estimate the distance between unknown nodes and beacon nodes. After acquiring the localization and the hop count of beacon nodes in the first stage, the average hop distance of whole networks can be computed. The information is then broadcast to the whole network, or all networks. Furthermore, most nodes are required to receive the average hop distance from their nearest beacon nodes. The distances between beacon nodes and unknown nodes can be calculated by multiplying the average hop distance by the hop count. Here,hdi and hij denote the average hop distance and the hop distance between a beacon node i xi,yi and an unknown node j xj,yj, respectively, as shown in the following formula:(1)hdi=∑xi−xj2+yi−yj2∑hij.
The distances between unknown nodes and beacon nodes are calculated using the following formula:(2)di=hdi×Hop,where hdi signifies the average hop distance, while Hop is the minimum hop count between unknown nodes i and beacon nodes.
As shown in Figure1, which shows the network topology of the DV-Hop localization algorithm, the red and the blue circles indicate beacon nodes and unknown nodes, respectively. The distances and hop counts among beacon nodes L1,L2,andL3 are known, and A represents an unknown node. According to formula (1), the average hop distance can be calculated as (40 + 75)/(2 + 5) = 16.42 m. In Figure 1, unknown node A receives the average hop distance from beacon node L2. On this basis, according to formula (2), the distances between the three beacon nodes L1,L2,andL3 and the unknown node A are 3 × 16.42 m, 2 × 16.42 m, and 3 × 16.42 m, respectively.Figure 1
Network topology.Step 3.
Based on plane geometry, the coordinates of unknown nodes can be acquired in the case of knowing the coordinates and distances between three beacon nodes. Suppose that the coordinates of three beacon nodes arex1,y1, x2,y2, and x3,y3, respectively, and the distances between these three beacon nodes and an unknown node D x,y are expressed as d1, d2, and d3, separately, then, the following formula is obtained:(3)x1−x2+y1−y2=d12,x2−x2+y2−y2=d22,x3−x2+y3−y2=d32.
Meanwhile, the coordinate of nodeD can be calculated by using the following formula:(4)xy=2x1−x32x2−x32y1−y32y2−y3−1x12−x32+y12−y32+d32−d12x22−x32+y22−y32+d32−d22.
In this way, the coordinates of unknown nodes can be computed. For a network topology established by a random arrangement of wireless sensor nodes, the paths from beacon nodes to unknown nodes are possibly not straight. Hence, some errors likely exist in the node localization process when using the DV-Hop algorithm. Moreover, the more numerous the hop counts, the larger the errors (i.e., error accumulation occurs).


### 2.2. Error Analysis for the DV-Hop Algorithm

The DV-Hop algorithm is based on the shortest path first mechanism. Nodes in WSNs broadcast their localization information and calculate distances to other nodes so that beacon nodes acquire the least hop counts required to reach other nodes and known position information. Meanwhile, the real paths between nodes are regarded as approximately straight lines to calculate the average hop distance, which is applied as the average hop distance of node localization in networks, while unknown nodes are expected to obtain the average hop distance from the nearest beacon nodes with favorable communication conditions to estimate their self-localization positions. Therefore, in the localization process, various factors can make localization errors exceed the actual demand. These factors include the fact that network nodes are distributed unevenly, the actual hop distances between nodes are far longer than, or less than, the communication radius, and there are no beacon nodes which can be used for communication near unknown nodes. However, the centroid localization algorithm [15] takes the coordinates of a polygon centroid as a reference position and has low requirements for the actual distances between nodes, the communication radius, and the density of beacon nodes. Therefore, the cost of network construction can be reduced by using the algorithm. Hence, the authors proposed a new DV-Hop localization algorithm based on the half-measure weighted centroid [16].


## 2.1. Basic Procedure of the DV-Hop Algorithm

The localization of nodes using the DV-Hop [12, 13] algorithm is mainly divided into three steps.Step 1.
Calculating the minimum hop count between beacon nodes and unknown nodes. Beacon nodes broadcast information which shows their positions to neighbouring nodes by using the classical distance vector routing protocol [14]. The information contains id,xi,yi,Hi, where id, xi,yi, and Hi represent the identifier, the coordinate, and the hop count of beacon nodes i, respectively. Moreover, the initial value of Hi is set to zero. The nodes receiving the broadcast information record the localization and hop counts of beacon nodes as vectors, which are then transmitted to neighbouring nodes (the value of hop count is incremented by one). When a node receives the same id group, it is supposed to compare the newly obtained value of Hi with the original value and then select the minimum value to replace and update the original group; otherwise, the newly obtained group is abandoned. The position information and minimum hop count of all beacon nodes are obtained by this communication mode in WSNs.Step 2.
Estimating the average hop distance. The purpose of calculating the average hop distance and minimum hop count first is to estimate the distance between unknown nodes and beacon nodes. After acquiring the localization and the hop count of beacon nodes in the first stage, the average hop distance of whole networks can be computed. The information is then broadcast to the whole network, or all networks. Furthermore, most nodes are required to receive the average hop distance from their nearest beacon nodes. The distances between beacon nodes and unknown nodes can be calculated by multiplying the average hop distance by the hop count. Here,hdi and hij denote the average hop distance and the hop distance between a beacon node i xi,yi and an unknown node j xj,yj, respectively, as shown in the following formula:(1)hdi=∑xi−xj2+yi−yj2∑hij.
The distances between unknown nodes and beacon nodes are calculated using the following formula:(2)di=hdi×Hop,where hdi signifies the average hop distance, while Hop is the minimum hop count between unknown nodes i and beacon nodes.
As shown in Figure1, which shows the network topology of the DV-Hop localization algorithm, the red and the blue circles indicate beacon nodes and unknown nodes, respectively. The distances and hop counts among beacon nodes L1,L2,andL3 are known, and A represents an unknown node. According to formula (1), the average hop distance can be calculated as (40 + 75)/(2 + 5) = 16.42 m. In Figure 1, unknown node A receives the average hop distance from beacon node L2. On this basis, according to formula (2), the distances between the three beacon nodes L1,L2,andL3 and the unknown node A are 3 × 16.42 m, 2 × 16.42 m, and 3 × 16.42 m, respectively.Figure 1
Network topology.Step 3.
Based on plane geometry, the coordinates of unknown nodes can be acquired in the case of knowing the coordinates and distances between three beacon nodes. Suppose that the coordinates of three beacon nodes arex1,y1, x2,y2, and x3,y3, respectively, and the distances between these three beacon nodes and an unknown node D x,y are expressed as d1, d2, and d3, separately, then, the following formula is obtained:(3)x1−x2+y1−y2=d12,x2−x2+y2−y2=d22,x3−x2+y3−y2=d32.
Meanwhile, the coordinate of nodeD can be calculated by using the following formula:(4)xy=2x1−x32x2−x32y1−y32y2−y3−1x12−x32+y12−y32+d32−d12x22−x32+y22−y32+d32−d22.
In this way, the coordinates of unknown nodes can be computed. For a network topology established by a random arrangement of wireless sensor nodes, the paths from beacon nodes to unknown nodes are possibly not straight. Hence, some errors likely exist in the node localization process when using the DV-Hop algorithm. Moreover, the more numerous the hop counts, the larger the errors (i.e., error accumulation occurs).


## 2.2. Error Analysis for the DV-Hop Algorithm

The DV-Hop algorithm is based on the shortest path first mechanism. Nodes in WSNs broadcast their localization information and calculate distances to other nodes so that beacon nodes acquire the least hop counts required to reach other nodes and known position information. Meanwhile, the real paths between nodes are regarded as approximately straight lines to calculate the average hop distance, which is applied as the average hop distance of node localization in networks, while unknown nodes are expected to obtain the average hop distance from the nearest beacon nodes with favorable communication conditions to estimate their self-localization positions. Therefore, in the localization process, various factors can make localization errors exceed the actual demand. These factors include the fact that network nodes are distributed unevenly, the actual hop distances between nodes are far longer than, or less than, the communication radius, and there are no beacon nodes which can be used for communication near unknown nodes. However, the centroid localization algorithm [15] takes the coordinates of a polygon centroid as a reference position and has low requirements for the actual distances between nodes, the communication radius, and the density of beacon nodes. Therefore, the cost of network construction can be reduced by using the algorithm. Hence, the authors proposed a new DV-Hop localization algorithm based on the half-measure weighted centroid [16].


## 3. Half-Measure Weighted Centroid Localization Algorithm

### 3.1. Improving the Algorithm

In computational geometry, the centroid of a polygon can be obtained by calculating the average coordinate of the vertices. Suppose that the position vector of a polygon withN edges satisfies the following equation, that is, pi=xi,yiT, then the coordinate Xest,Yest of its centroid [17, 18] is expressed as shown below:(5)Xest,Yest=1N∑iNXi,1N∑iNY.Theorem 1.
Given the network nodeG with N nodes, the node density and the node distribution follow the two-dimensional Possion point process with density; to ensure that the probability P (G connectivity) p≥0≤p<1 is established, the optimal communication radius of nodes is(6)Rmin=−ln1−P1/Nρπ.Certificate.If the network G is connected, ∀i∈V, i, it is not an isolated node; that is, the node degree di≥1, then the minimum node degree of graph G dmin≥1.Because nodes are distributed as two-dimensional Poisson points,(7)Pdi=0=PNπR2i=0=ρπR2i00!e−ρπR2i=e−ρπR2i.Therefore,Pdi≥1=1−Pdi=0=1−e−ρπR2i.According to the independence of Poisson process events,(8)Pdmin≥1=NNPdi≥1NPdi=00=1−e−ρπR2iN.Therefore, according to the probability P (G connectivity)≥p0≤P≤1, then 1−e−ρπR2iN≥p, and it can be reasoned. Ri≥−ln1−p1/N/ρπ, and the minimum communication radius of nodes can be obtained, Rmin=−ln1−P1/N/ρπ·QED.Definition 1.
Regions are chosen, the neighbourhoodh of node M∈Rn relative to node set S is(9)UM;h=y∈S,M−y1<h/2.
The advantage of using 1-norm is saving calculation time, so square regions are chosen.Definition 2.
Theα-order node density of node M relative to set S is(10)1hM;S,α.
In the equation,(11)hS;M,α=minh:UM,h,thenodenumberisαatleasta, Since M's neighbourhood hS;M,α is an open set, so it has at least α−1 nodes in the node set S.Definition 3.
AssumeMi as the neighbourhood set of node i, Mij as the Euclidean distance between node i and node j, R as the network communication radius, then the neighbourhood distance model is(12)Mi=j∣j≠ianddij≤R.Definition 4.
AssumeMi and Mj are chance variables in a network of random uniform distribution, there exists Mi≠Mj, Mijis all the nodes within the common area of Mi & Mj, i.e., Mij=Mi∩Mj, then the neighbourhood distance NDi,j is(13)NDi,j=1−mijMj,j∈R.
There may existMi≠Mj, NDi,j≠NDj,i, but dij=dji, and the neighbouthood distance CHNDi,j of half-measure weighted centroid proposed in this paper is(14)CHNDi,j=12NDi,j+NDj,i=1−Mi+Mj2MiMjmij.


#### 3.1.1. Half-Measure Weighted Centroid Localization Communication Model

The adopted log-normal shadow fading model is an empirical model based on experiments:(15)pd=pd0−10nplogdd0+Xσ.Theoretically, the weight factor reflects the influence of all beacon nodes on centroid position. The positioning weightweighti is(16)weighti=1dij^g,i∈U,where dij^ is the estimated distance between unknown node i and beacon node j. However, g is the weight factor (Figure 2).Figure 2
Weight factor.


#### 3.1.2. Localization Model

Assume pathS1,Sn to be the path from node S1 to node Sn, Si and Si+1 are neighbours, and the localization distance of path S1,Sn is(17)RNDpathS1+Sn=∑i=1n−1RNDSi,Si+1.Path betweenS1 and Sn is not unique, but there exists a shortest path that satisfies the RNDpathS1,Sn value. Assume RNDminS1,Sn to be the shortest RND path distance,(18)RNDmin=∑i=1n−1RNDSi,Si+1.Choose the optimized weight within the communication range of unknown nodes and calculatedij, the estimated distance from the unknown node i to the beacon node j is(19)dij=RNDSi,Sj×weighti.Calculating error and accuracy, while calculating the average hop distance,K beacon nodes adjacent to beacon nodes i xi,yi are searched to obtain error factors, which are expressed by errori, as shown in formula:(20)errori=∑i=1kxi−xj2+yi−yj2K.Calculating the localization accuracy for the centroid ofa beacon node i, denoted as accuracyi, and then, the normalized average localization error:(21)accuracyi=erroriR.


#### 3.1.3. Computing Coordinates of Nodes

By using the least squares method (LSM), the distance from the unknown nodei xi,yi to beacon node jxj,yj is calculated, and then the distance dij between the two nodes can be calculated from the following formula:(22)dij=xi−xj2+yi−yj2.Accordingly,(23)xi2+yi2−2xiyi+xj2+yj2=dij2.Let,(24)Ai=xi2+yi2,Bj=xj2+yj2.Then,(25)dij2−Ai=−2xiyj−2xjyi+Bj.It can be found from formula (20) that(26)Z=xjyj⋮Bj,A=−2x1−2y11−2x2−2y21⋮⋮⋮2xi−2yi1,B=d12−A1d22−A2⋮di2−Ai.The coordinates of the nodes are(27)B=A×Z,Z=ATA−1ATB,unknown node j is(28)xj=Z1,1,yj=Z2,1.


### 3.2. Procedures of the Improved Algorithm

Step 1.
The hop count in the shortest path is acquired by broadcasting information among nodes, which is the same as the procedure used in the DV-Hop localization algorithm.Step 2.
Based on half-measure weighted centroid neighbourhood distance model, calculate neighbourhood distance, weight factor, shortest path, and optimize.Step 3.
The distances from the unknown nodes to the beacon nodes are calculated by using formulas (6)–(25). Then, by using LSM, the coordinates of unknown nodes are obtained, and the flowchart is shown in Figure 3.Figure 3
Flowchart.


## 3.1. Improving the Algorithm

In computational geometry, the centroid of a polygon can be obtained by calculating the average coordinate of the vertices. Suppose that the position vector of a polygon withN edges satisfies the following equation, that is, pi=xi,yiT, then the coordinate Xest,Yest of its centroid [17, 18] is expressed as shown below:(5)Xest,Yest=1N∑iNXi,1N∑iNY.Theorem 1.
Given the network nodeG with N nodes, the node density and the node distribution follow the two-dimensional Possion point process with density; to ensure that the probability P (G connectivity) p≥0≤p<1 is established, the optimal communication radius of nodes is(6)Rmin=−ln1−P1/Nρπ.Certificate.If the network G is connected, ∀i∈V, i, it is not an isolated node; that is, the node degree di≥1, then the minimum node degree of graph G dmin≥1.Because nodes are distributed as two-dimensional Poisson points,(7)Pdi=0=PNπR2i=0=ρπR2i00!e−ρπR2i=e−ρπR2i.Therefore,Pdi≥1=1−Pdi=0=1−e−ρπR2i.According to the independence of Poisson process events,(8)Pdmin≥1=NNPdi≥1NPdi=00=1−e−ρπR2iN.Therefore, according to the probability P (G connectivity)≥p0≤P≤1, then 1−e−ρπR2iN≥p, and it can be reasoned. Ri≥−ln1−p1/N/ρπ, and the minimum communication radius of nodes can be obtained, Rmin=−ln1−P1/N/ρπ·QED.Definition 1.
Regions are chosen, the neighbourhoodh of node M∈Rn relative to node set S is(9)UM;h=y∈S,M−y1<h/2.
The advantage of using 1-norm is saving calculation time, so square regions are chosen.Definition 2.
Theα-order node density of node M relative to set S is(10)1hM;S,α.
In the equation,(11)hS;M,α=minh:UM,h,thenodenumberisαatleasta, Since M's neighbourhood hS;M,α is an open set, so it has at least α−1 nodes in the node set S.Definition 3.
AssumeMi as the neighbourhood set of node i, Mij as the Euclidean distance between node i and node j, R as the network communication radius, then the neighbourhood distance model is(12)Mi=j∣j≠ianddij≤R.Definition 4.
AssumeMi and Mj are chance variables in a network of random uniform distribution, there exists Mi≠Mj, Mijis all the nodes within the common area of Mi & Mj, i.e., Mij=Mi∩Mj, then the neighbourhood distance NDi,j is(13)NDi,j=1−mijMj,j∈R.
There may existMi≠Mj, NDi,j≠NDj,i, but dij=dji, and the neighbouthood distance CHNDi,j of half-measure weighted centroid proposed in this paper is(14)CHNDi,j=12NDi,j+NDj,i=1−Mi+Mj2MiMjmij.


### 3.1.1. Half-Measure Weighted Centroid Localization Communication Model

The adopted log-normal shadow fading model is an empirical model based on experiments:(15)pd=pd0−10nplogdd0+Xσ.Theoretically, the weight factor reflects the influence of all beacon nodes on centroid position. The positioning weightweighti is(16)weighti=1dij^g,i∈U,where dij^ is the estimated distance between unknown node i and beacon node j. However, g is the weight factor (Figure 2).Figure 2
Weight factor.


### 3.1.2. Localization Model

Assume pathS1,Sn to be the path from node S1 to node Sn, Si and Si+1 are neighbours, and the localization distance of path S1,Sn is(17)RNDpathS1+Sn=∑i=1n−1RNDSi,Si+1.Path betweenS1 and Sn is not unique, but there exists a shortest path that satisfies the RNDpathS1,Sn value. Assume RNDminS1,Sn to be the shortest RND path distance,(18)RNDmin=∑i=1n−1RNDSi,Si+1.Choose the optimized weight within the communication range of unknown nodes and calculatedij, the estimated distance from the unknown node i to the beacon node j is(19)dij=RNDSi,Sj×weighti.Calculating error and accuracy, while calculating the average hop distance,K beacon nodes adjacent to beacon nodes i xi,yi are searched to obtain error factors, which are expressed by errori, as shown in formula:(20)errori=∑i=1kxi−xj2+yi−yj2K.Calculating the localization accuracy for the centroid ofa beacon node i, denoted as accuracyi, and then, the normalized average localization error:(21)accuracyi=erroriR.


### 3.1.3. Computing Coordinates of Nodes

By using the least squares method (LSM), the distance from the unknown nodei xi,yi to beacon node jxj,yj is calculated, and then the distance dij between the two nodes can be calculated from the following formula:(22)dij=xi−xj2+yi−yj2.Accordingly,(23)xi2+yi2−2xiyi+xj2+yj2=dij2.Let,(24)Ai=xi2+yi2,Bj=xj2+yj2.Then,(25)dij2−Ai=−2xiyj−2xjyi+Bj.It can be found from formula (20) that(26)Z=xjyj⋮Bj,A=−2x1−2y11−2x2−2y21⋮⋮⋮2xi−2yi1,B=d12−A1d22−A2⋮di2−Ai.The coordinates of the nodes are(27)B=A×Z,Z=ATA−1ATB,unknown node j is(28)xj=Z1,1,yj=Z2,1.


## 3.1.1. Half-Measure Weighted Centroid Localization Communication Model

The adopted log-normal shadow fading model is an empirical model based on experiments:(15)pd=pd0−10nplogdd0+Xσ.Theoretically, the weight factor reflects the influence of all beacon nodes on centroid position. The positioning weightweighti is(16)weighti=1dij^g,i∈U,where dij^ is the estimated distance between unknown node i and beacon node j. However, g is the weight factor (Figure 2).Figure 2
Weight factor.


## 3.1.2. Localization Model

Assume pathS1,Sn to be the path from node S1 to node Sn, Si and Si+1 are neighbours, and the localization distance of path S1,Sn is(17)RNDpathS1+Sn=∑i=1n−1RNDSi,Si+1.Path betweenS1 and Sn is not unique, but there exists a shortest path that satisfies the RNDpathS1,Sn value. Assume RNDminS1,Sn to be the shortest RND path distance,(18)RNDmin=∑i=1n−1RNDSi,Si+1.Choose the optimized weight within the communication range of unknown nodes and calculatedij, the estimated distance from the unknown node i to the beacon node j is(19)dij=RNDSi,Sj×weighti.Calculating error and accuracy, while calculating the average hop distance,K beacon nodes adjacent to beacon nodes i xi,yi are searched to obtain error factors, which are expressed by errori, as shown in formula:(20)errori=∑i=1kxi−xj2+yi−yj2K.Calculating the localization accuracy for the centroid ofa beacon node i, denoted as accuracyi, and then, the normalized average localization error:(21)accuracyi=erroriR.


## 3.1.3. Computing Coordinates of Nodes

By using the least squares method (LSM), the distance from the unknown nodei xi,yi to beacon node jxj,yj is calculated, and then the distance dij between the two nodes can be calculated from the following formula:(22)dij=xi−xj2+yi−yj2.Accordingly,(23)xi2+yi2−2xiyi+xj2+yj2=dij2.Let,(24)Ai=xi2+yi2,Bj=xj2+yj2.Then,(25)dij2−Ai=−2xiyj−2xjyi+Bj.It can be found from formula (20) that(26)Z=xjyj⋮Bj,A=−2x1−2y11−2x2−2y21⋮⋮⋮2xi−2yi1,B=d12−A1d22−A2⋮di2−Ai.The coordinates of the nodes are(27)B=A×Z,Z=ATA−1ATB,unknown node j is(28)xj=Z1,1,yj=Z2,1.


## 3.2. Procedures of the Improved Algorithm

Step 1.
The hop count in the shortest path is acquired by broadcasting information among nodes, which is the same as the procedure used in the DV-Hop localization algorithm.Step 2.
Based on half-measure weighted centroid neighbourhood distance model, calculate neighbourhood distance, weight factor, shortest path, and optimize.Step 3.
The distances from the unknown nodes to the beacon nodes are calculated by using formulas (6)–(25). Then, by using LSM, the coordinates of unknown nodes are obtained, and the flowchart is shown in Figure 3.Figure 3
Flowchart.


## 4. Simulation and Data Analysis

### 4.1. Establishing a Network Simulation Environment

Assess the efficacy and practicability of the improved algorithm proposed here, carry out system level simulation with MATLAB software and analyze and compare test data. One hundred wireless sensor nodes are arranged randomly in a square region of 100 m × 100 m, including 40 beacon nodes and 60 unknown nodes. Other parameters are set as shown in Table1.Table 1
Simulation parameters.
Area of the square region: BorderLength = 100
Total number of network nodes: NodeAmount = 100
Number of beacon nodes: BeaconAmount = 40
Number of unknown nodes: UNAmount = NodeAmount−BeaconAmount
The communication radius of each sensor:R = 50
The number of network nodes generated at random:C=BorderLength.∗rand(2, NodeAmount)
A matrix for storing the coordinates of network nodes: Sxy = [1: NodeAmount; C]
A matrix containing the coordinates of beacon nodes: Beacon = [Sxy(2,1: BeaconAmount); Sxy(3,1:BeaconAmount)]
A matrix containing the coordinates of unknown nodes: UN = [Sxy(2,(BeaconAmount + 1):NodeAmount); Sxy(3,(BeaconAmount + 1):Node amount)]


### 4.2. Simulation and Performance Analysis

The network topology of the DV-Hop localization algorithm based on the half-measure weighted centroid. Thereinto, the red ○ and the black + denote beacon nodes and unknown nodes, respectively (Figure4). Distance estimation between unknown nodes and beacon nodes is obtained by the product of the minimum hop and the average hop distance between the two nodes; however, the minimum number of hops between nodes is largely determined by the communication radius of the nodes. Different communication radii will have different hop distances, which will also lead to different node locations; as shown in Figures 4(a)–4(c), the larger the node density, the smaller the communication radius, and the topology is closer to the actual location. In addition, optimizing network topology can save network energy consumption and prolong network lifetime.Figure 4
Network topology. (a) Same communication radius. (b) Different communication radii. (c) Same communication radius, but different densities.
(a)
(b)
(c)The localization errors arising from the DV-Hop localization algorithm and the proposed localization algorithm are compared over the same communication radius (R = 50 m), and the node localization error of the DV-Hop localization algorithm fluctuates within the range 15 to 60, while that of the proposed algorithm ranges between 2 and 15 and is more stable. The main reason is that the increase of the number of unknown nodes will reduce the minimum communication radius. The number of unknown nodes is equivalent to the total number of nodes (fewer beacon nodes) which is an important factor affecting the current network connectivity. The localization errors arising from the DV-Hop localization algorithm and the proposed localization algorithm are compared over the same communication radius (R = 50 m), and the node localization error of the DV-Hop localization algorithm fluctuates within the range 15 to 60, while that of the proposed algorithm ranges between 2 and 15 and is more stable (Figure 5).Figure 5
Comparison of the localization errors over the same communication radius.It shows the comparison of average localization accuracy of DV-Hop algorithm with that of the proposed localization algorithm. It shows that the localization accuracy of the DV-Hop localization algorithm varies within the range 0.3 to 1.2, while that of the improved localization algorithm fluctuates between 0.1 and 0.2. The main reason is that the location accuracy of New DV-Hop algorithm is higher with the increase of the number of communication radius (Figure6).Figure 6
Comparison of the localization accuracies over the same communication radius.The comparison of the average localization errors arising from the DV-Hop localization algorithm with those of the proposed localization algorithm under different communication radii is done. A total of 100 groups of experiments were carried out as the communication radiusR was increased from 10 m to 80 m. In the new DV-Hop localization algorithm, when the node communication radius increases, the positioning accuracy is smaller and the positioning performance is better (Figure 7).Figure 7
Comparison of localization errors over different communication radii.The localization accuracy of the DV-Hop algorithm are compared with that of the DV-Hop localization algorithm based on the half-measure weighted centroid, and other DV-Hop. To obtain the results, 100 groups of experiments were conducted with increasing communication radiusR (10 m ≤ R ≤ 80 m) (Figure 8).Figure 8
Comparison of localization accuracies over different communication radii.At the same communication radius, and for different densities of beacon nodes, the comparison of the average localization errors of the two algorithms is done. Similarly, the communication radiusR was fixed at 50 m, while the number of beacon nodes was increased from 10 to 80 in the 50 groups of experiments. The average localization error of the DV-Hop algorithm increased gradually from 30. While other DV-Hop localization algorithm is about 15, and the new DV-Hop localization algorithm based on a half-measure weighted centroid was below 5; in particular, its localization performance was optimal for between 30 and 60 beacon nodes. It is almost unaffected by the communication radius and the total number of nodes. The main reason is that the more accurate distance between beacon nodes and their neighbours can be obtained by optimizing equations (13) and (14), which can undoubtedly reduce the positioning error of all unknown nodes (Figure 9).Figure 9
Comparison of the average localization errors at the same communication radius, and different densities of beacon nodes.The comparison of localization accuracies of the two algorithms at the same communication radius, but for different densities of beacon nodes, is done. The communication radiusR was set to 50 m, and the number of beacon nodes was increased gradually from 10 to 80 in the 50 groups of experiments. Compared with the DV-Hop algorithm, whose localization accuracy increases from 0.6 to 0.7, other DV-HOP is about 0.3; and new DV-Hop shows a localization accuracy fluctuating stably within 0.1. Beacon nodes are calculated by the half-measure weighted centroid localization model, next step is to design optimized weight, and optimize the shortest path. The higher the density of beacon nodes and the more reasonable the distribution, the higher the positioning accuracy and the better the positioning performance (Figure 10).Figure 10
Comparison of the localization accuracies at the same communication radius, but with different densities of beacon nodes.


## 4.1. Establishing a Network Simulation Environment

Assess the efficacy and practicability of the improved algorithm proposed here, carry out system level simulation with MATLAB software and analyze and compare test data. One hundred wireless sensor nodes are arranged randomly in a square region of 100 m × 100 m, including 40 beacon nodes and 60 unknown nodes. Other parameters are set as shown in Table1.Table 1
Simulation parameters.
Area of the square region: BorderLength = 100
Total number of network nodes: NodeAmount = 100
Number of beacon nodes: BeaconAmount = 40
Number of unknown nodes: UNAmount = NodeAmount−BeaconAmount
The communication radius of each sensor:R = 50
The number of network nodes generated at random:C=BorderLength.∗rand(2, NodeAmount)
A matrix for storing the coordinates of network nodes: Sxy = [1: NodeAmount; C]
A matrix containing the coordinates of beacon nodes: Beacon = [Sxy(2,1: BeaconAmount); Sxy(3,1:BeaconAmount)]
A matrix containing the coordinates of unknown nodes: UN = [Sxy(2,(BeaconAmount + 1):NodeAmount); Sxy(3,(BeaconAmount + 1):Node amount)]


## 4.2. Simulation and Performance Analysis

The network topology of the DV-Hop localization algorithm based on the half-measure weighted centroid. Thereinto, the red ○ and the black + denote beacon nodes and unknown nodes, respectively (Figure4). Distance estimation between unknown nodes and beacon nodes is obtained by the product of the minimum hop and the average hop distance between the two nodes; however, the minimum number of hops between nodes is largely determined by the communication radius of the nodes. Different communication radii will have different hop distances, which will also lead to different node locations; as shown in Figures 4(a)–4(c), the larger the node density, the smaller the communication radius, and the topology is closer to the actual location. In addition, optimizing network topology can save network energy consumption and prolong network lifetime.Figure 4
Network topology. (a) Same communication radius. (b) Different communication radii. (c) Same communication radius, but different densities.
(a)
(b)
(c)The localization errors arising from the DV-Hop localization algorithm and the proposed localization algorithm are compared over the same communication radius (R = 50 m), and the node localization error of the DV-Hop localization algorithm fluctuates within the range 15 to 60, while that of the proposed algorithm ranges between 2 and 15 and is more stable. The main reason is that the increase of the number of unknown nodes will reduce the minimum communication radius. The number of unknown nodes is equivalent to the total number of nodes (fewer beacon nodes) which is an important factor affecting the current network connectivity. The localization errors arising from the DV-Hop localization algorithm and the proposed localization algorithm are compared over the same communication radius (R = 50 m), and the node localization error of the DV-Hop localization algorithm fluctuates within the range 15 to 60, while that of the proposed algorithm ranges between 2 and 15 and is more stable (Figure 5).Figure 5
Comparison of the localization errors over the same communication radius.It shows the comparison of average localization accuracy of DV-Hop algorithm with that of the proposed localization algorithm. It shows that the localization accuracy of the DV-Hop localization algorithm varies within the range 0.3 to 1.2, while that of the improved localization algorithm fluctuates between 0.1 and 0.2. The main reason is that the location accuracy of New DV-Hop algorithm is higher with the increase of the number of communication radius (Figure6).Figure 6
Comparison of the localization accuracies over the same communication radius.The comparison of the average localization errors arising from the DV-Hop localization algorithm with those of the proposed localization algorithm under different communication radii is done. A total of 100 groups of experiments were carried out as the communication radiusR was increased from 10 m to 80 m. In the new DV-Hop localization algorithm, when the node communication radius increases, the positioning accuracy is smaller and the positioning performance is better (Figure 7).Figure 7
Comparison of localization errors over different communication radii.The localization accuracy of the DV-Hop algorithm are compared with that of the DV-Hop localization algorithm based on the half-measure weighted centroid, and other DV-Hop. To obtain the results, 100 groups of experiments were conducted with increasing communication radiusR (10 m ≤ R ≤ 80 m) (Figure 8).Figure 8
Comparison of localization accuracies over different communication radii.At the same communication radius, and for different densities of beacon nodes, the comparison of the average localization errors of the two algorithms is done. Similarly, the communication radiusR was fixed at 50 m, while the number of beacon nodes was increased from 10 to 80 in the 50 groups of experiments. The average localization error of the DV-Hop algorithm increased gradually from 30. While other DV-Hop localization algorithm is about 15, and the new DV-Hop localization algorithm based on a half-measure weighted centroid was below 5; in particular, its localization performance was optimal for between 30 and 60 beacon nodes. It is almost unaffected by the communication radius and the total number of nodes. The main reason is that the more accurate distance between beacon nodes and their neighbours can be obtained by optimizing equations (13) and (14), which can undoubtedly reduce the positioning error of all unknown nodes (Figure 9).Figure 9
Comparison of the average localization errors at the same communication radius, and different densities of beacon nodes.The comparison of localization accuracies of the two algorithms at the same communication radius, but for different densities of beacon nodes, is done. The communication radiusR was set to 50 m, and the number of beacon nodes was increased gradually from 10 to 80 in the 50 groups of experiments. Compared with the DV-Hop algorithm, whose localization accuracy increases from 0.6 to 0.7, other DV-HOP is about 0.3; and new DV-Hop shows a localization accuracy fluctuating stably within 0.1. Beacon nodes are calculated by the half-measure weighted centroid localization model, next step is to design optimized weight, and optimize the shortest path. The higher the density of beacon nodes and the more reasonable the distribution, the higher the positioning accuracy and the better the positioning performance (Figure 10).Figure 10
Comparison of the localization accuracies at the same communication radius, but with different densities of beacon nodes.


## 5. Conclusion

In view of the disadvantages in the practical application of the DV-Hop algorithm in WSNs, such as the uneven distribution of nodes, holes, and large errors in the average hop distance, a novel localization algorithm, combining the DV-Hop algorithm with a half-measure weighted centroid, was proposed. Beacon nodes realize their localization by using the centroid algorithm and then use the localized accuracy as the weight for localizing unknown nodes. Through theoretical reasoning and simulation experiments, it was found that the improved localization algorithm reduced the localization errors and improved the localization accuracy of unknown nodes compared with the DV-Hop algorithm whether used in the same networks or not. Compared with the DV-Hop algorithm, whose localization accuracy increases from 0.6 to 0.7, other DV-HOP is about 0.3; and new DV-Hop shows a localization accuracy fluctuating stably within 0.1. It was worth noting that the study was performed in an ideal network simulation environment, so there remains the need to research the application of the improved algorithm under realistic network environments in the future.



---

*Source: 9892512-2019-01-03.xml*