Wireless sensor network (WSN) possesses very broad application prospect in many fields, where the node location technology is one of the key technologies of WSN. Distance vector hop (DV-Hop) localization algorithm is a widely used algorithm in this technology, and it uses routing exchange protocol to make unknown nodes obtain beacon node information which will be used for coordinate calculation, therefore there exists certain error for the algorithm itself. Aiming at the disadvantage of large error existing in the traditional wireless sensor network location algorithm based on DV-Hop, an improved DV-Hop algorithm based on hop thinning and distance correction is proposed. The minimum hop is corrected by introducing received signal strength indication (RSSI) ranging technology, and the average hop distance is corrected by weighted average value of hop distance error and estimated distance error. Subsequently, the overall improvement on the location performance of the Hop-DV location algorithm is realized, and the location error is reduced. Under the Matlab simulation environment, the simulation experiment on the improved algorithm is carried out. The experimental results show that the improved algorithm reduces the location error and has higher location accuracy.
Notes
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Abbreviations
DV-Hop
Distance vector hop
RSSI
Received signal strength indication
WSN
Wireless sensor network
1 Introduction
Wireless sensor network (WSN) is a self-organizing network composed of a large number of sensor nodes, which presents a high intersection degree between multiple disciplines and can be used in many harsh and unsuitable environments for human work [1]. The location of the event or the node location to obtain information is the important information in the monitoring message of sensor nodes. Moreover, the monitoring data without location information is always meaningless. Then, the location information of sensor nodes is very important for wireless sensor networks [2]. Therefore, the design of localization system and algorithm suitable for the characteristics of wireless sensor networks has become a research hotspot in the field of wireless sensor networks.
In view of a few nodes with known locations, the localization of sensor nodes is to determine their own locations according to a certain localization mechanism. Based on whether it needs to measure the distance or angle between nodes in the location process, the existing location algorithms can be divided into two categories: distance-based location algorithm and distance-free location algorithm [3]. Distance-based algorithm has high location accuracy; however, it has a very high requirement on hardware resources. Moreover, it requires strict clock synchronization among its nodes and leads to high cost. In contrast, distance-free location algorithm has better practicability because it does not need measuring distance [4].
Advertisement
As a location algorithm without measuring distance, distance vector hop (DV-Hop) algorithm was proposed by Niculescu D et al. The algorithm uses routing exchange protocol to make unknown nodes obtain beacon node information which will be used to calculate their own coordinates. Because the algorithm is simple and easy to be implemented, and the coordinates of unknown nodes can be obtained without additional hardware, it becomes the most widely used algorithm in location algorithm without measuring distance.
In recent years, many scholars at home and abroad have done a lot of in-depth researches on DV-Hop algorithm, and proposed different approaches to improve the algorithm in view of its shortcomings, which have improved the location accuracy and performance of the algorithm. In ref. [5], when the distance between unknown node and beacon nodes was calculated, the average hop distance from its nearest beacon nodes was adopted, but the influence of the average hop distance from other beacon nodes was not taken into account; therefore, it existed certain error. In ref. [6], after calculating the average hop distance of the beacon nodes in the whole network, the distance from other beacon nodes was calculated by using this distance. Moreover, a deviation value was obtained by subtracting the calculated distance from the actual distance, and it was used to weigh the average hop distance. Reference [7] used the least square method based on curve fitting to solve the coordinates of unknown nodes, and then optimized the coordinates of unknown nodes. Reference [8] constructed the location problem as a least square problem with constraints, and then calculated the coordinates of unknown nodes by quadratic programming. Reference [9] proposed that the average of the maximum and minimum hop distance of beacon nodes could be used as the average hop distance of the nodes to be located, which effectively improved the positioning accuracy. In ref. [10], an improved algorithm for re-estimation of beacon node position was proposed. This algorithm used DV-Hop to re-estimate beacon node position to obtain error, and then used the optimal algorithm to find the optimal value of hop distance to improve the positioning accuracy. Reference [11] proposed to use convex programming to find the location estimation of the nodes to be located, and then cooperated with the nodes in several iterations to improve the location estimation of all the nodes to be measured. Compared with the APIT algorithm, it had more accurate location results. Reference [12] proposed a novel DV-Hop algorithm, which eliminated one of the steps and did not need to count the hops of unknown nodes, and this algorithm had higher location efficiency, lower communication cost, and no additional hardware, but its complexity was higher.
Aiming at the disadvantage of large error existing in the traditional wireless sensor network location algorithm based on DV-Hop, this paper proposes an improved DV-Hop algorithm based on hop thinning and distance correction. The minimum hop is corrected by introducing received signal strength indication (RSSI) ranging technology, and the average hop distance is corrected by weighted average value of hop distance error and estimated distance error. Subsequently, the overall improvement on the location performance of the Hop-DV location algorithm is realized, and the location error is reduced.
2 Principle and error analysis of traditional DV-Hop location algorithm
2.1 The principle of traditional DV-Hop location algorithm
The idea of DV-hop algorithm is that, the minimum hop and the average hop distance between unknown nodes and beacon nodes are obtained by means of beacon node broadcasting. Then, the product of minimum hop and the average hop distance is used to estimate the distance, and the location of unknown nodes is estimated by trilateral measurement or maximum likelihood estimation.
Advertisement
DV-Hop localization algorithm calculates the position coordinates of the nodes to be located, and it usually divided into the following stages:
1.
Determining the minimum hop
Through the controllable flooding algorithm, the beacon node in the network broadcasts its location data packet to the whole network. After receiving the information from the beacon node, the neighbor node increases the hop value in the packet by one hop, and then forwards it to the next neighbor node. The receiving node only keeps the smaller hop value information from the same beacon node, but ignores the information packet of larger hop number. After flooding, all nodes will get the minimum path and hop value of each beacon node.
2.
Determining the distance between unknown nodes and beacon nodes
Let the average hop distance between beacon node i and other beacon node j (j≠i) be HopSizei, which is shown as Eq. (1).
Where (xi,yi) and (xj,yj) respectively represents the coordinate value of beacon nodes i and j, and hopj is the hop value between beacon nodes i and j (j≠i).
Then, the beacon node sends HopSizei to the network. The node to be located only records the average hop distance of the first nearest beacon node and forwards it to the neighbor node.
Assume the coordinates of unknown node u is (xu,yu), the first beacon node recorded by unknown node u is t, and the average hop distance is HopSizet. Let the coordinate of any beacon node i (i≠j) be (xi,yi). Then, the actual hop distance between the node to be located and the beacon node is shown in Eq. (2).
$${d}_{ui}={hop}_{ui}\times {HopSize}_t$$
(2)
Where u and i are variables, and t is a constant.
3.
Determining the coordinates of unknown nodes
When the distance between an unknown node and three or more beacon nodes is obtained, the maximum likelihood method can be used to solve its own coordinates. Suppose that the coordinates of m beacon nodes are denoted as A(xk,yk), where k = 1, 2,... m, m > 3, the unknown node of the coordinates to be determined is U(x, y), and the calculated distances between beacon nodes and unknown node are d1, d2, …, dm, respectively. Taking the maximum likelihood method as an example, the coordinates of U are solved. According to the distance relationship between unknown node and beacon nodes, the following equations can be obtained:
For AX = b, the estimated coordinates of unknown nodes are obtained by least square method, and the calculation formula of coordinates of U is shown in Eq. (6):
$$X={\left({A}^TA\right)}^{-1}{A}^Tb$$
(6)
In order to get a clearer understanding on the coordinate calculation principle of unknown nodes, this paper further explains the principle of DV-Hop algorithm through Fig. 1.
Fig. 1
Network topology diagram
×
Where i, j, and k in the network topology diagram all represent beacon nodes, u0, u1,..., u5 denotes the unknown nodes, and the distance between any two of i, j, and k are represented by dij, dik and djk respectively. According to the principle of DV-Hop algorithm, the minimum hop between beacon nodes i and j are 6, the minimum hop between i and k are 5, and the minimum hop between j and k are 2. Therefore, the average hop distance of i, j, k can be calculated separately.
Suppose the unknown node whose position is to be determined is u3. As can be seen from Fig. 1, the hop value between u3 and k is the smallest, so the average hop distance of k is used as HopSizek when calculating the distance between u3 and i, j, and k. Because the minimum hop values between u3 and i, j, and k are 4, 3, and 1 respectively. The product of the average hop distance and the hop value is regarded as the distance between two nodes, so the distance between u3 and i, j, and k can be calculated respectively.
Now, we can use the tripartite method to find the coordinates of u3.
2.2 The error analysis of traditional DV-Hop location algorithm
DV-Hop algorithm makes the unknown node obtain the average hop distance and the hop value information of beacon node through routing exchange protocol. Then, the unknown node estimates its own coordinates through these information, so there must be some errors in the obtained coordinates.
1.
The error of hop value
In the practical application of wireless sensor networks, the nodes are randomly and unevenly deployed in a given monitoring area. Therefore, for a beacon node, there are many unknown nodes in its communication radius, and the distance between these unknown nodes and the beacon node is not completely equal. However, when the distance between them is calculated according to the principle of DV-Hop algorithm, the obtained results are equal. The reason is that, within the communication radius of the beacon node, the hop values between all unknown nodes and the beacon node will be recorded as 1 hop, and these unknown nodes are closest to the beacon node. Therefore, when calculating the distance from the beacon node, they use the average hop distance broadcasted by the beacon node. Because the product of hop value and average hop distance between two nodes is regarded as the distance between two nodes, which makes the distance between these unknown nodes and beacon nodes be equal. Taking Fig. 2 as an example, all the hop values between unknown nodes u0, u1, ..., u5 and beacon node i are 1 hop. Moreover, when calculating the distance between these unknown nodes and beacon nodes, the average hop distance HopSize of beacon node i is employed, so there are:
$${d}_{u_ki}={HopSize}_i\times 1,k=0,1,\dots, 5$$
(9)
Fig. 2
Distribution diagram of unknown nodes within the communication radius of beacon nodes
×
Then, we can get:
$${d}_{u_0i}={d}_{u_1i},\Lambda, ={d}_{u_5i}$$
(10)
This is not matched with the actual distance value between unknown nodes u0, u1, ..., u5 and beacon node i. In fact, the distance between them should satisfy the following relationship:
$${d}_{u_0i}<{d}_{u_1i}\Lambda <{d}_{u_5i}$$
(11)
As can be seen from Fig. 2, the distance between u0, u1, ..., u5 and node i is quite different, so it is necessary to adjust the hop value between them according to the distance between nodes, instead of simply recording all the hops as 1.
2.
The error of average hop distance
When calculating the distance between the unknown node and the beacon node, the average hop distance from the nearest beacon node is adopted, so the rationality of the average hop distance determines the location error of the unknown node. Taking Fig. 3 as an example, the influence of average hop distance on distance calculation between unknown nodes and beacon nodes is illustrated. Where i, j, and k represent beacon nodes, numbers 1, 2,..., 8 represent unknown nodes, and the communication radius between any two nodes is set as R. As can be seen from Fig. 3, the ideal hop value between beacon node i and beacon node j is only slightly greater than one hop, but the hop value between beacon node i and beacon node j is 4 due to the random distribution of nodes. For beacon node j and beacon node k, their ideal hop value are about 3, but the actual network topology shows that the hop value between them is 6. According to the principle of DV-Hop algorithm, the average hop distance of j can be calculated as (‖ij‖ + ‖jk‖)/(4 + 6). However, in ideal case, the average hop distance of j is about (‖ij‖ + ‖jk‖)/(1 + 3). Therefore, the actual average hop distance calculated is less than the average hop distance in ideal case. For the unknown nodes 3 and 4 which are nearest to the beacon node, they use the average hop distance to calculate the distance between them and beacon node j, which is expressed by (‖ij‖ + ‖jk‖)/(4 + 6) × 1 ≈ 4R/10. Meanwhile, the actual distance between unknown nodes 3 and 4 and beacon node j is almost R, so the calculated distance is far less than the actual distance. Similarly, the average hop distances of beacon nodes i and k are different from the actual average hop distances, so employing the average hop distance of unknown nodes will also cause errors when calculating the distance between unknown nodes and beacon nodes.
3.
The calculation error of node position
Fig. 3
Network topology diagram for an example
×
Because the distance data between unknown nodes and beacon nodes is obtained by means of estimation, there is a certain deviation between the estimated distance and the actual distance. If the method used in calculating the coordinates of unknown nodes is inappropriate, the error may further increase.
Maximum likelihood estimation error analysis diagram is showed as Fig. 4.
Fig. 4
Maximum likelihood estimation error analysis diagram
×
The positioning error by means of maximum likelihood method is illustrated by Fig. 4. Suppose A1(x1,y1), A2(x2,y2),..., Am(xm,ym) are the beacon nodes, the unknown node is U(x, y), and the estimated distance between the unknown node and the beacon nodes is d1, d2, …, dm, whose errors compared with the actual distances are ε1,ε2.….εm, respectively. Therefore, the following equations can be obtained from the relationship between the actual distance and the estimated distance:
Where \({\gamma}_k^2=\pm 2{d}_k{\varepsilon}_k+{\varepsilon}_k^2\), k ∈ [1, m − 1]. Therefore, due to the existence of the above error term, the error in the new equation is larger than that of any of the original two subtractive equations. Therefore, the error between the coordinates of unknown nodes obtained by this method and the actual values increases.
3 DV-Hop location algorithm based on minimum hop thinning and average distance correction
Based on the above analysis on error problem, this paper improves the DV-Hop algorithm by using minimum hop thinning and average hop distance correction.
Where d is the distance between any two nodes that need to measure distance, d0 is a reference distance between two nodes, Pr(d) represents a power corresponding to distance d, Pr(d0) represents a power corresponding to distance d0, k0 is a path loss factor, and its value is generally set between 2 and 6.
In Eq. (15), a random noise with a mean of 0 and a standard deviation of σ is introduced, and X is generally used to represent the random distribution. If the distance from the transmitting end is d, the receiving power of the receiving end will be Pr(d)dB, where dB represents power and d0 = 1m. Meanwhile, if the average RSSI value of A receiving end is 1m from the transmitting end, the RSSI value at d from the transmitting end will be deduced from Eq. (15):
$${P}_r(d)=A-10{k}_0\lg d+{X}_{\sigma }$$
(16)
Generally, the RSSI value decreases along with the increasing distance from the transmitter. Therefore, unknown nodes can calculate the distance from beacon nodes by using RSSI value. Next, according to the above method, the hop value of DV-Hop location algorithm will be corrected.
1.
Grading the first hop
In this paper, the general idea of improving the hop value is to weigh the hop value h1 of the first hop. The ideal distance of the first hop is the communication radius R, which is the same as all nodes in the whole network. Therefore, by grading the communication radius R, each stage corresponds to a hop value, which can reduce the impact of hops on positioning error and improve positioning accuracy.
Let the communication radius of the node be R, and the distance (not the hop distance) between the node and its neighbor node be x. When the hop number of the first hop is counted as h1 and the first hop is divided into m levels, the hop number of the first hop is shown in Eq. (17).
In the actual application process, there is no way to obtain distance. Equation (16) reflects the relationship between distance and power, so there is \(\frac{\left(i-1\right)R}{m}<x\le \frac{iR}{m}\), where the corresponding RSSI value is concerned as seen in Eq. (18).
In practical applications, the power caused by Gauss noise is very small, which is smaller than the power value corresponding to the first hop, so the influence of Gauss noise on the hop value can be completely ignored. From Eqs. (17) and (18), the relationship between the hop number of the first hop and the receiving power of the corresponding sensor node can be obtained as seen in Eq. (19).
Equation (19) classifies the first hop of sensor node according to the attenuation intensity of RSSI signal. This method makes the hop value of traditional DV-Hop algorithm become decimal, which improves the positioning accuracy of the nodes to be positioned and reduces the error. At the same time, the hop value h1 of the first hop can be used to correct the rest of the hops.
2.
Weighting the hop value
Define the weight: If the hop value between sensor nodes in the network is greater than 1 hop, then the weight Hj is defined as the ratio of the distance dj of j hop measured by RSSI technology to the first hop distance d1, which can be seen in Eq. (20).
$${H}_j=\frac{d_j}{d_1}$$
(20)
Where j is a positive integer.
According to Eq. (15), Eq. (20) is further transformed to obtain the relationship between distance and receiving power. The RSSI received by the receiving node at distance d from the sending node is represented by Pr(d)dB, as shown in Eq. (21).
Equation (22) is the weight calculation formula of hop value between nodes. Moreover, the weight must be the weight of the hop value between the node and its neighbors. By multiplying the weight with the hop value h1 of the first hop, the hop value of this hop can be obtained, and the distance between sensor nodes in the whole network can be corrected.
3.2 Average distance correction
If the number of beacon nodes in the monitoring area is n, the average hop distance of each beacon node in the whole network will be calculated by Eq. (1). Let the average hop distance of all beacon nodes be recorded as Davg as shown in Eq. (23).
Let the difference between the average hop distance of beacon node i and the Davg value calculated by Eq. (23) be recorded as Di1, which is shown in Eq. (24).
Let the difference between the actual distance and the estimated distance between beacon nodes i and j in the whole network be recorded as Di2, which is shown in Eq. (25).
Among them, dij is the actual distance between beacon node i and j. \({\hat{d}}_{ij}={HopSize}_i\times {hop}_{ij}\) is the estimated distance between beacon node i and j; hopij is the minimum hop between beacon node i and j.
If the weight of beacon node i is ωi, the error coefficient of this beacon node will be obtained by Eqs. (25) and (26), and the weight ωi can be obtained by using this error coefficient, as shown in Eq. (26).
Let the average hop distance of the re-estimated beacon node i be Avginew, which is a weighted value of the error coefficient of each beacon node in the whole network. Moreover, it is calculated by combing with Eq. (27), and is shown in Eq. (28).
If the coordinates of unknown node and beacon node are (xk,yk) and (xi,yi) respectively, the hop distance from unknown node k to beacon node i will be shown in Eq. (29).
$${d}_{ki}={hop}_{ki}\times {Avg}_{inew}$$
(29)
Where k and i are variables.
4 Experiment results and analysis
In Matlab environment, 200 sensor nodes are randomly distributed in a square area of 200 m × 200 m. The proportion of initial beacon nodes to total nodes increases from 0.05 to 0.3, the communication radius R = 30 m. The relationship between the average positioning error of the whole network and the proportion of initial beacon nodes is shown in Fig. 5. Figure 5 shows that the average positioning error of the two algorithms decreases with the increase of the proportion of beacon nodes. Furthermore, under the same proportion of beacon nodes, the average positioning error of the DV-Hop algorithm in this paper is smaller than that of the traditional DV-Hop algorithm.
Fig. 5
The relationship between the average positioning error and the proportion of initial beacon nodes
×
Under the same environment, 200 sensor nodes are randomly distributed in the square area of 200 m × 200 m. The proportion of beacon nodes to total nodes is 0.1. The communication radius R increases from 15 to 40 m. The relationship between the average positioning error of the whole network and the communication radius of the nodes is shown in Fig. 6. Figure 6 shows that the average positioning error of the two algorithms decreases with the increase of the communication radius of the nodes. When the communication radius reaches a certain value, the decline trend of the average positioning error of the whole network is gradually smooth. Moreover, when the communication radius is the same, the average positioning error of the DV-Hop algorithm in this paper is less than that of the traditional DV-Hop algorithm.
Fig. 6
The relationship between the average positioning error and the communication radius of the nodes
×
5 Conclusion
Aiming at the disadvantage of large error existing in the traditional wireless sensor network location algorithm based on DV-Hop, this paper proposes an improved DV-Hop algorithm based on hop thinning and distance correction. The minimum hop is corrected by introducing RSSI ranging technology, and the average hop distance is corrected by weighted average value of hop distance error and estimated distance error. The experimental results show that the improved algorithm reduces the location error and has higher location accuracy.
Acknowledgements
Not applicable.
Competing interests
The author declares that he has no competing interest.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
