Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.05.2013 | Ausgabe 1/2013 Open Access

Telecommunication Systems 1/2013

An improvement of DV-Hop localization algorithm for wireless sensor networks

Zeitschrift:
Telecommunication Systems > Ausgabe 1/2013
Autoren:
Yu Hu, Xuemei Li
Wichtige Hinweise
The authors gratefully acknowledge the support of the Shanxi Natural Science Foundation.

1 Introduction

With the high-speed development of the information industry today, Wireless sensor network (WSN) is produced and developed based on sensor technology, MEMS (Micro-Electro-Mechanism System) technology and wireless communications technology. It has been widely used in national defense, environmental monitoring, traffic management, health care, manufacturing, anti-terrorism and other disaster areas, and its low power consumption, low cost, distributed and self-Characteristics of the organization have brought a revolution in information perception.
Wireless sensor network is a new technology about acquiring and processing information, it can self-organize network topology structure. The nodes can monitor and collect various environmental or monitoring object information through collaborative work in real time, and process the information at the same time. In wireless sensor network, there is no location information is meaningless, so the node localization problem is one of the important common support technology in the wireless sensor networks and is highly regarded [ 1].
Localization algorithms for static wireless sensor networks are usually classified along several axes. A first distinction between localization algorithms deals with the use of anchor nodes. Network of nodes where no anchors are used usually establish their relative positions, possibly creating their own coordinate system. In general, the more anchors, the better the accuracy of the estimated locations. However, deploying anchors can be a tedious task and prove to be a rather expensive way of improving the accuracy of the localization algorithm. According to whether measures the actual distance between nodes in the positioning process, localization algorithm can be divided into: Range-based localization algorithm Range-free and localization algorithm.
Range-based localization algorithms use techniques such as radio signal strength indicator [ 2, 3] (RSSI) or radio and ultrasound with angle-of-arrival (AOA) or time-difference-of-arrival (TDOA), to measure the distance that separates an unlocalized node from an anchor. These distances, also called ranges, are sensitive to range errors, i.e., inaccuracies in the range measurements and often rely on additional hardware. To be independent of hardware and counter range inaccuracies, researchers developed range-free methods that depend uniquely on the information location, hop count-a node receives from its neighbors, be they anchors or regular nodes. And it includes centroid, convex programming, DV-Hop, Amorphous, MDS-MAP and APIT.
The Range-free needs low cost, and has high survival ability, positioning accuracy basically can satisfy the needs of practical application, so it has more practical value and development prospect, and it is one of the emphasis of research at the same time [ 4, 5].

2 DV-Hop algorithm

DV-Hop algorithm was made by Dragons Niculescu from the Lutegesi University of United States etc., the basic idea is: the node itself only exchange information with its adjacent nodes, the distance between the unknown nodes and the anchor nodes is represented by the product of network average Hop distance and the shortest path between two nodes,and uses trilateral measurement to obtain the node location information [ 6, 7]. This algorithm requires some nodes have GPS positioning equipment, other nodes determines their own position according to anchor node (using GPS positioning or manual deployment of the nodes in advance, their exact location is known) and the communication information between the nodes. The nodes don’t need have distance measurement or Angle measurement function, also do not need additional location or Angle measuring equipment. So DV-Hop algorithm is one of the most widely applied algorithm in the large node self-localization algorithms for wireless sensor network.
DV-HOP algorithm can be divided into the following 3 steps [ 8, 9]:
Step 1. Calculate the minimal hops between unknown nodes and every anchor node.
Beacon nodes broadcast their location information packet to the neighbor, which included jumping section of the field, and the value is initialized to 0. Receiving node records the minimum hop count of each node, while ignoring the larger hop group from the same anchor node, then the jump number is added 1 and transmitted to neighbor nodes.
Step 2. Calculate the actual distance between unknown nodes and the anchor nodes.
Each anchor node estimates the actual average hop distance using formula ( 1), according to the location information and the hop count of the other anchor nodes.
$$ \textit{HopSize}_{i} = \frac{\sum_{i \ne j} \sqrt{( x_{i} - x_{j} )^{2} + ( y_{i} - y_{j})^{2}}}{\sum_{i \ne j} h_{j}} $$
(1)
Among them: ( x i , y i ), ( x j , y j ) are the coordinates of the anchor node i, j; h j  is the hop account between anchor node iand the anchor node j( ij).
Anchor nodes broadcast the average hop distance which use the grouping with a live field to the network. Unknown nodes, which only record the first received average hop distance and transmit the information to neighbor nodes. Then unknown nodes calculates the distance to every anchor node, according to the records of hop account.
Step 3. Calculate the coordinates of unknown nodes.
The unknown nodes use trilateration or maximum likelihood estimation method to calculate the coordinates of the unknown nodes,according to the records of hop distance to each anchor node, using the trilateral value or maximum likelihood estimation method to calculate the unknown nodes of coordinates.
When the distances which are from all the anchor nodes to the unknown node  P, we can use formula ( 2) to calculate:
$$ \left\{ \begin{array} {@{}l} ( x_{1} - x )^{2} + ( y_{1} - y )^{2} = d_{1}^{2} \\ \vdots \\ ( x_{n} - x )^{2} + ( y_{n} - y )^{2} = d_{n}^{2} \end{array} \right. $$
(2)
Meanwhile, formula ( 2) can be expressed as:
$$ \left\{ \begin{array}{@{}l} x_{1}^{2} - x_{n}^{2} + 2 ( x_{1} - x_{n} )x + y_{1}^{2} - y_{n}^{2} \\ - 2 ( y_{1} - y_{n} )y = d_{1}^{2} - d_{n}^{2} \\ \vdots \\ x_{n - 1}^{2} - x_{n}^{2} + 2 ( x_{n - 1} - x_{n} )x + y_{n - 1}^{2} - y_{n}^{2} \\ - 2 ( y_{n - 1} - y_{n} )y = d_{n - 1}^{2} - d_{n}^{2} \end{array} \right. $$
(3)
Formula ( 3) means the linear equation for:
$$ AX = B $$
(4)
Among them:
$$\begin{aligned} &{A = \left[ \begin{array}{@{}l@{\quad}l} 2( x_{1} - x_{n}) & 2( y_{1} - y_{n})\\ \vdots & \\ 2(x_{n - 1} - x_{n}) & 2( y_{n - 1} - y_{n}) \end{array} \right]}\\ &{B = \left[ \begin{array}{@{}l} x_{1}^{2} - x_{n}^{2} + y_{1}^{2} - y_{n}^{2} + d_{n}^{2} - d_{1}^{2} \\ \vdots\\ x_{n - 1}^{2} - x_{n}^{2} + y_{n - 1}^{2} - y_{n}^{2} + d_{n}^{2} - d_{n - 1}^{2} \end{array} \right]} \\ &{X = \left[ \begin{array}{@{}c@{}} x \\ y \end{array} \right]} \end{aligned}$$
We can get the coordinates of the unknown node  P through using the standard minimum mean variance estimation method to formula ( 5):
$$ X = \bigl(A^{T} A\bigr)^{ - 1}A^{T}b $$
(5)

3 An improved scheme for DV-HOP algorithm

As shown in Fig.  1, the process of the improved algorithm can be as follows:

3.1 The improvement for average hop distance of unknown nodes

The second step for DV-Hop algorithm, each anchor node gets the other anchor nodes’ location and minimum number of hops, and calculates their average hop distance, then each anchor node broadcasts their average hop distance as a correction to the network. The original algorithm, the use of strategy is to ensure the vast majority unknown node receives average hop distance from the nearest anchor node, that is, the node records only the first average hop distance received. However, there will be a great error that using the nearest anchor node’s average hop distance instead of the average hop distance of all the anchor nodes that involved in the localization.
Therefore, in the improved algorithm, using part of the anchor nodes to estimate the average hop distance of the unknown nodes, and these anchor nodes have great effect to the average hop distance of the unknown node. How to choose the anchor nodes becomes a key problem. Therefore, it introduces the threshold M in the improved algorithm, if the number of hops between an anchor node and the unknown node is greater than the threshold  M, then gives up the anchor node when calculating the unknown node’s average hop distance, otherwise, it uses a weighted method to calculate each unknown node’s average hop distance. The method to choose threshold M is as follows [ 10]:
$$ \frac{1}{R}\sqrt{\frac{A \times LH}{TN \times LP \times p}} < M < H_{\max} $$
(6)
Among them: A is the area of the network; LH is the average number of anchor nodes for the need of locating each unknown node, it depends on the total number of nodes in the network; TN is the total number of nodes in the network; LP is the percentage of anchor nodes; H max is the maximum number of minimum hops between unknown node to anchor node.
On this basis, value of M should try to meet the need to locate all the unknown nodes and choose the minimum, so that the network communication is relatively small. It should be noted, formula ( 6) is the range of M in the ideal case, it is difficult that the nodes distribute very uniformly in the network, so the threshold M should be appropriately increased to meet the overall network coverage.
Weighted average hop distance is calculated: For example, the average hop distance of unknown node is  S, the number of hops between anchor node  i and the unknown nodes is H i . Assuming the unknown node received the information from anchor nodes, each anchor node weighted value of average hop distance is denoted as W i , calculate it as formula ( 7). Namely the weighted value of anchor node i is the value that the reciprocal of the unknown node to the anchor node i divides the sum of reciprocals of hops which the unknown node to each anchor node. These weights were then normalized to get:
$$ W_{i} = \left\{ \begin{array}{@{}l@{\quad}l} \frac{1 / H_{i}}{\sum_{j = 1}^{n} \frac{1}{H_{j}}}, & H_{i} \le M \\ 0, & H_{i} > M \end{array} \right. $$
(7)
According to the average hop distance of every anchor node  S i , calculate the average hop distance of unknown nodes as formula ( 8).
$$ S = \sum_{i = 1}^{n} W'_{i}S_{i} $$
(8)
Namely the unknown node’s average hop distance equals to the sum of products that the weighted value multiply the average hop distance of every anchor node. So the average hop distance of every unknown node will be estimated more accurately through the weighted processing. It is more accurate and better to reflect the average hop distance of network.

3.2 Position correction

In order to further improve the precision, the improved algorithm, it needs to estimate the location of each anchor node. To make the unknown nodes that have been estimated coordinate information as anchor nodes, and make the anchor nodes as unknown nodes, in order to estimate the coordinates of anchor nodes. For example, an anchor node  B, using its average hop distance multiplies the hops between it and the unknown node to get the distance between the anchor node and the unknown node, and then using maximum likelihood estimation method to estimate the anchor node’s position. Then it compares this result to the actual location of  B, and obtains the correction factor. The calculation method is as follows:
$$ \begin{array}{@{}l} x_{i} = x_{a} - x_{b} \\ y_{i} = y_{a} - y_{b} \end{array} $$
(9)
( x a , y a ) is the actual location for the anchor node B, ( x b , y b ) is estimated location for  B. When the anchor node’s own correction factor are obtained, then the anchor node broadcast the correction factor to network. An unknown node receives all the correction factor of the anchor nodes, these correction factors are weighted and calculate the average correction factor. Specific process is as follows (assuming the number of anchor nodes in the network is  n):
$$ W_{j} = \frac{1 / H_{j}}{\sum_{i = 1}^{n} \frac{1}{H_{i}}} $$
(10)
These weights were then normalized to get \(W_{j}'\), then calculate the average correction factor:
$$ \begin{array}{@{}l} \displaystyle x = \sum _{j = 1}^{n} \bigl(W_{j}^{\prime} \times x_{j}\bigr) \\ \displaystyle y = \sum_{j = 1}^{n} \bigl(W_{j}^{\prime} \times y_{i}\bigr) \end{array} $$
(11)
Then use the following equation for the unknown node’s position correction:
$$ \begin{array}{@{}l} x' = x + x \\ y' = y + y \end{array} $$
(12)
Among them, ( x, y) is the average correction factor for the network, ( x, y) is the original estimated location for the unknown nodes, ( x′, y′) is the corrected location for the unknown nodes.

4 Algorithm simulation

In order to test the performance of the improved algorithm, using MATLAB to simulate and analyze the traditional DV-HOP algorithm and the improved algorithm. As shown in Fig.  2, the nodes distribute in 100 m×100 m Square area, the unknown nodes and anchor nodes are randomly distributed in the area. Communication range of each node are set to 50 m. Below respectively discussing anchor node density, node density and thresholds M for the influence of the positioning error, each performance of the simulation were randomized 100 times.

4.1 The influence of anchor node on the positioning error

The number of nodes in the network is 100, the number of anchor nodes are taken 10, 15, 25, 25, 30, 35, 40, namely the proportion of anchor nodes are 10 %, 15 %,…,40 %, comparing the influence of average location error for traditional DV-Hop Algorithm and improved DV-Hop algorithm in different proportion of anchor nodes.
As shown in Fig.  3, with the percentage of anchor nodes increases, the average positioning error of two algorithms show a decreasing trend. Under the same conditions, the average location error of the improved algorithm is smaller than conventional DV-Hop algorithm. It can be seen from the figure, when the anchor nodes in 10–25 % ratio, the positioning error of the improved algorithm decreased greatly, when the anchor node ratio is greater than 25 %, the positioning error of the improved algorithm tends to stability.

4.2 The impact of total number of nodes on positioning error

Let the total number of nodes in the network are 100,110,120,…,300, the number of anchor nodes is 15. In the case of the other conditions remain unchanged, we compares the average location error of the traditional and improved DV-Hop algorithm, and then analyzes the influence of the total number of nodes on the node location error in the network.
As shown in Fig.  4, with the total number of nodes in the network increasing, the location errors of the traditional DV-Hop algorithm and improved algorithm are increased. However, under the same conditions, the positioning error of the improved algorithm is smaller than the traditional DV-Hop algorithm—the average positioning error is reduced about 15 %. So we can know that the improved algorithm is more preponderant than the traditional DV-Hop algorithm.

4.3 The effect of threshold M on the positioning error

The number of nodes in the network is 100, the number of the anchor nodes is 15, the threshold value are taken in 3, 4, 5, 6, 7, 8 in the improved algorithm. It can be seen from Table  1, comparing with the traditional DV-HOP algorithm, the improved algorithm reduces the positioning error. However, it reduces the positioning error significantly different when taking different threshold.In this experiment, we can see the positioning error is smallest as M=6. So, it is not good that the threshold M gets too big or too small, we must choose the threshold M suitably according to the actual situation of network.
Table 1
The effect of threshold M on the positioning error
Threshold M
Positioning error (%)
Traditional DV-HOP algorithm
Improved DV-HOP algorithm
3
25.53
24.25
4
25.53
24.68
5
25.53
24.46
6
25.53
20.32
7
25.53
23.29
8
25.53
21.21

5 Conclusion

This paper summarized the characteristics of the DV-Hop algorithm based on the analysis of DV-Hop algorithm, and presented an improved localization algorithm. Through theoretical analysis and experimental results, it can be seen that the improved algorithm significantly increases the positioning accuracy of the nodes compared with conventional DV-HOP algorithm, under the premise of maintaining simple, low cost. It is an effective scheme for the node localization in wireless sensor networks.

Acknowledgement

This work was financially supported by the Shanxi Natural Science Foundation (2009011019-2).
Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2013

Telecommunication Systems 1/2013 Zur Ausgabe