# Improved DV-Hop Location Algorithm Based on Mobile Anchor Node and Modified Hop Count for Wireless Sensor Network

Authors: Jia Yanfei; Zhang Kexin; Zhao Liquan
Journal: Journal of Electrical and Computer Engineering
 (2020)

---

## Abstract

To improve the performance of location accuracy for wireless sensor network, a new location algorithm based on mobile anchor node and modified hop count is proposed. Firstly, we set different communication powers for all nodes to make them have different communication ranges. This makes the relationship between the hop count and real distance more accurate. Secondly, the unknown node computes the mean distance per hop between it and the three anchor nodes that are the nearest to the unknown node and uses the mean value as the mean distance per hop. Finally, we suppose that some anchor nodes can move. Once the position of some anchor nodes changes, we recalculate the positions of unknown nodes and use the mean value of recorded positions as position of unknown nodes. Simulation results show that the proposed method has lower location error than other methods.


---

## Body

## 1. Introduction

Wireless sensor network is one of the important parts of Internet of Things (IOT) [1–5]. It has been applied in many fields and plays an important role in national defence, industry, smart medicine, and smart home [6, 7]. Wireless sensor network consists of many sensor nodes that are distributed randomly in some range. They collect information and transmit it to monitor centre. If we do not have the position information of sensor nodes, the collected information will not have any value. Therefore, it is very important to get the position information of sensor nodes. Sensor nodes can be divided the two types that are the unknown node and the anchor node. The anchor node has its own position information by using the global positioning system (GPS) module. The position information of unknown node without GPS can be estimated by using some location methods for wireless sensor networks based on the position information of the anchor node [8].The location methods for unknown sensor nodes have two types that are range-based algorithm and range-free algorithm [9]. The range-based location method relays on the additional devices such as sound sensors or aerial, which can obtain the precise physic information such as the distance or angle of sensor nodes. It includes Time of Arrival (TOA) method [10, 11], Time Difference of Arrival (TDOA) method [12], and Angle of Arrival (AOA) method [13]. Although the method of range-based algorithm has a higher accuracy, the additional devices are expensive and consume large amounts of energy [14]. These limit its application range.The range-free location method uses the position information of anchor nodes to estimate the position of the unknown node. It does not require additional devices. Although it has lower accuracy than the range-based algorithm, it is more suitable for most of wireless sensor network. Therefore, we mainly focus on the range-free location method. The typical range-free location methods include Centroid method [15], Approximate Point in Triangulation Test (APIT) method [16, 17], and DV-Hop method [18]. The Centroid method utilizes anchor nodes of surrounding the unknown node to form a geometric figure, and if the unknown node is in the range of geometric figure, the mean coordinate of these anchor nodes will be used as unknown node’s estimated coordinate. The accuracy of the estimation position depends on the ratio of anchor nodes. The method has a bigger error for estimating unknown node position. The APIT method selects three anchor nodes to form a triangle. If the unknown node is in the triangle, it will record the coordinate of these anchor nodes and use the mean coordinate of the three anchor nodes as estimated coordinate of unknown node. The APIT method has a better performance than Centroid method, but the error is also larger. For Centroid and APIT method, if the unknown node is in the edge of the workspace, it will be difficult to estimate unknown node position. The DV-Hop method depends on the relationships of hop count and the mean distance per hop to estimate unknown node position. It has a lower complexity and is easily to implement. In this paper, we mainly focus on the DV-Hop algorithm to estimate the position for the unknown node.DV-Hop algorithm is a typical range-free location algorithm and has been researched in recent years. Many related algorithms based on DV-Hop have been proposed. The authors of [19, 20] improve the DV-Hop from two parts, one is to make the hop count be more accurate, and the other one is to modify the estimation distance from the unknown node to each anchor node. It has a better performance in locating unknown node. To improve location performance, the authors in [21, 22] suppose that the anchor node can move and correct the hop count by setting the hop count threshold when the anchor nodes move.


## 2. Principle of DV-Hop Algorithm

DV-Hop algorithm uses the hop counts between unknown node and anchor nodes and the mean distance per hop of anchor nodes to estimate the position of unknown node. The nodes are distributed in workspace and these nodes can communicate with each other. If a node can communicate with other nodes directly, we consider that the hop count is 1. Anchor nodes broadcast the position and identify some other information to the workspace. If the sensor node is in the anchor node communication range, it will receive the information directly. On the contrary, it receives the information by other nodes relying. The information includes anchor node’s identity, anchor node’s position coordinate, anchor node communication power, and the hop count (the initial value is 0). If a node receives the information, the hop count will add 1 and update the information. The node conserves the information and transmits the updated information with the same communication power to other nodes.Although a sensor node can receive the same information from the same anchor node, the route is different. The hop counts may be different for different routes. Therefore, the sensor nodes select the minimum hop count as the final hop count. After all anchor nodes broadcast information, anchor nodes can compute the minimum hop count between anchor nodes. According to the hop count and real distance which is obtained by GPS between anchor nodes, it can compute the mean distance per hop of anchor node. The mean distance per hop of anchor node is computed by(1)ahopi=∑j≠ixi−xj2+yi−yj2∑j≠ihi,j,where xi,yi and xj,yj are the coordinates of anchor nodes i and j, hi,j is the minimum hop count from anchor node i to anchor node j, and ahopi is the mean distance per hop of anchor node i.The unknown sensor node only receives the information which is sent by the anchor node that is nearest to it. The information constrains the mean distance per hop of anchor node. The unknown sensor node receives the information and uses mean distance per hop and hop count between the unknown sensor node and anchor node to compute the distance between the unknown sensor node and anchor node. The distance is computed by(2)dk,i=ahopi×hk,i,where dk,i is the distance between the unknown sensor node k and anchor node i, ahopi is the distance per hop of anchor node i, and hk,i is the hop count between the unknown sensor node k and anchor node i.The unknown sensor node uses the distances between itself and at least three anchor nodes to locate its position by least square method [23]. The position of unknown node can be estimated by solving(3)dk,12=xk−x12+yk−y12,dk,22=xk−x22+yk−y22,⋯dk,i2=xk−xi2+yk−yi2,where dk,i is the distance between the unknown sensor node k and anchor node ixi,yi is the real coordinate of anchor node ii=1,2,…,n, and xk,yk is the estimated coordinate of unknown nodes k. Based on (3), we can get(4)x12−xi2−2x1−xixk+y12−yi2−2y1−yiyk=dk,12−dk,i2,x22−xi2−2x2−xixk+y22−yi2−2y2−yiyk=dk,22−dk,i2,⋯xi−12−xi2−2xi−1−xixk+yi−12−yi2−2yi−1−yiyk=dk,i−12−dk,i2.It is expressed as matrix, that is(5)AX=B,A=2×x1−xix2−xi⋯y1−yiy2−yi⋯xi−1−xiyi−1−yi,B=x12−xi2+y12−yi2+dk,i2−dk,12x22−xi2+y22−yi2+dk,i2−dk,22⋯xi−12−xi2+yi−12−yi2+dk,i2−dk,i−12,where X=xk,ykT is the estimation coordinate of unknown node k; the position of unknown node k can be calculated by using(6)X=ATA−1ATB.


## 3. The Proposed Method

In the DV-Hop algorithm, the communication ranges of all nodes are fixed, and the hop count between nodes is 1 in the same communication range. We suppose that the communication radius isR. If the distance between node A and B is R and between node C and D is 0.5R, the hop counts are the same between A and B and between C and D. The distances for two pair nodes are different, but they have the same hop counts. This will affect the location accuracy of DV-Hop algorithm. To overcome the problem, we introduce the variable communication power to the location algorithm. We suppose that each node has three different communication powers. It can be realized by some methods which can be seen in [19–21]. Therefore, the three communication ranges can be set as 0–0.3R, 0–0.6R, and 0–0.9R, where R is the maximum communication range. The hop counts that are corresponding to the different communication ranges are 0.2, 0.5 and 0.8, respectively.The anchor nodes firstly broadcast information that includes anchor node identifier, anchor node coordinate, communication power, and hop count (initial value is 0) to workspace with minimum communication power. In the sensor nodes in the communication range of anchor node, the hop count between the sensor node and anchor node will increase by 0.2. The sensor node updates information and then relays the updated information with the same communication power. Secondly, the anchor nodes broadcast information with higher communication power, and the hop count between the sensor node and anchor node increases by 0.5. In the end, the anchor nodes broadcast information with the highest communication power, and the hop count between the sensor node and anchor node increases by 0.8. After broadcasting information, we compute the minimum hop count between anchor nodes under the same communication power. We can obtain three hop count values between two anchor nodes for different communication power and select the minimum value as hop count between two anchor nodes. We use the hop count between anchor node and the other anchor nodes and their real distance to compute the mean distance per hop of the anchor node. It can be realized by (1).The estimated distance between two anchor nodes is obtained by mean distance per hop and hop count. There will be a difference between the estimated distance and real distance. The mean distance per hop is an average value and has little error. Therefore, the error for estimated distance is mainly caused by hop count. To reduce the error, we introduce a modifying factor to the hop count. We suppose that the mean distance per hop of anchor nodei is ahopi that is obtained by (1) and the hop count between the anchor node i and anchor node j is hi,j. The estimated distance is(7)dei,j=ahopi×hi,j.The real distance is(8)dri,j=xi−xj2+yi−yj2,where dri,j is the real distance from the anchor node i to anchor node j and xi,yi and xj,yj are the coordinates of anchor node i and j, respectively. Based on the estimated distance and real distance, we deduce the modified factor of hop count for anchor node i. That is,(9)ehi=1R×n−1×∑j≠idri,j−dei,j,where R is the maximum communication range and n is the number of anchor nodes. Therefore, the hop count based on modified factor is(10)Hk,i=hk,i+ehi,where hk,i is the hop count between the unknown sensor node k and anchor node i. ehi is the modified factor in (9). Hk,i is the modified hop count between the unknown sensor node k and anchor node i. After all sensor anchor nodes estimating the mean distance per hop and computing the modified factor, the anchor nodes broadcast the information which includes mean distance per hop, modified factor, and identifier to workspace.In the DV-Hop algorithm, the unknown node directly uses the mean distance per hop of anchor node which is the nearest the unknown node as mean distance per hop. In the location process, it will use at least three anchor nodes to estimate its position. It uses the same mean distance per hop to compute the distances between the unknown sensor node and different anchor nodes. Different anchor nodes may have different mean distance per hop. Therefore, it will introduce large error into the computing distance. To solve the problem, we average the mean distance per hop of three anchor nodes which have the smallest hop counts between anchor nodes and the unknown sensor nodek and use it as mean distance per hop of unknown node k. It is expressed as(11)hopk=1∑i=13hk,i∑i=13hk,i×ahopi,where hk,i is the hop count between the unknown sensor node k and anchor sensor node i and ahopi is the mean distance per hop of anchor sensor node i. Based on (10) and (11), we can obtain the distance dk,i between the unknown sensor node k and anchor sensor node i. That is,(12)dk,i=Hk,i×hopk.We also use at least three anchor nodes to estimate the position of unknown sensor node based on (3) and (12). To further reduce the location error, we introduce the mobile anchor into location. We suppose that the anchor node i is mobile. The anchor node i firstly moves randomly in the workspace, and the moving distance is fixed for one time. Before it moves to the new position, it will determine whether or not the new position is in the workspace. If it is in the workspace, the anchor node moves to the new position and then the unknown sensor node uses (3) and (12) to estimate the position of unknown sensor node. Otherwise, the anchor node randomly regenerates a new position and also determines the new position whether or not it is in the workspace. It moves to the new position, until the new position is in the workspace. Once the position of anchor node is changed, the unknown node will estimate the position and save the position. In the end, it averages the estimated positions and uses it as the position of unknown node.


## 4. Results and Discussion

We use the relative error as performance index to evaluate the proposed method and other methods [19–21]. The relative error can be expressed as(13)error=1n×R∑k=1nxk−xr2+yk−yr2,where xk,yk and x,ryr are the estimated position and real position of unknown node k, respectively. n is the number of unknown nodes, and R is the maximum communication radius. We suppose that the sensor nodes are randomly distributed in a square area whose length of side is 100 meters, and the number of sensor nodes is 100.


### 4.1. Only One Anchor Node Can Move for the Proposed Method with Moveable Anchor Node

In this section, the number of moveable anchor nodes is only one node for the proposed method with moveable anchor node. For example, if the number of anchor nodes is 10, then the moveable anchor node is 1 and the unmovable anchor node is 9 in the proposed method with moveable anchor node. Figure1 shows the relationship between the relative error and number of simulations with the condition that the number of anchor nodes is 10 and the maximum communication distance is 50 meters. From Figure 1, we can see that the proposed method with movable anchor node has the smallest relative error, and the next are the proposed method with unmovable anchor node and the method proposed in [19], respectively. The method proposed in [21] has the biggest relative error, and next is the method in [20]. Figure 2 shows the relationship between the average relative error and communication radius with the condition that the number of anchor nodes is 10 and the number of simulations is 10000. From Figure 2, we can see that the proposed method with movable anchor node has the smallest relative error, and the next is the proposed method with the unmovable anchor node for the different communication radius. The method proposed in [21] still has the biggest relative error, and next is the proposed method in [19, 20], respectively. Based on Figures 1 and 2, they show that the two proposed methods still have better performance in error than the proposed methods in [19–21] in different number of simulations and communication radius.Figure 1
The relative error with different number of simulations.Figure 2
The average relative error with different communication radius.Figures3–5 show the average relative error with different number of anchor nodes and maximum communication radius. The maximum communication radius is 30 m, 50 m, and 70 m for Figures 3–5, respectively. The number of simulations is 10000 times. From Figures 3–5, we can see that the average relative errors of all methods reduce with the increasing of the number of anchor nodes for the same communication radius. In Figure 3, the proposed method with movable anchor node has the smallest average relative error, and the next is, respectively, the proposed method with unmovable anchor node. Although the proposed method in [19] has the bigger average relative error than the proposed method in [20] when the number of anchor nodes is 4, it has smaller average relative error than the proposed method in [20] for other different numbers of anchor nodes. On the whole, the proposed method in [19] has the smaller average relative error than other proposed methods in [20, 21].Figure 3
The average relative error with different number of anchor nodes and communication radius 30 meters.Figure 4
The average relative error with different number of anchor nodes and communication radius 50 meters.Figure 5
The average relative error with different number of anchor nodes and communication radius 70 meters.In Figure4, our two proposed methods still have the smaller error than others. The proposed method in [21] has the biggest error; next is, respectively, the proposed method in [19, 20]. In Figure 5, when the number of anchor nodes is less than 4, the proposed method with unmovable node has the highest relative average error, and when the number of anchor nodes is more than 4, the proposed method with unmovable node has smaller average relative error than others except for the proposed method with movable anchor node. Although the proposed method in [19] has bigger error than method in [20] when the number of anchor nodes is less than 4, it has smaller error than method in [20] for other different numbers of anchor nodes. On the whole, the proposed method in [21] has biggest error; next is the method in [19, 20]. Therefore, Figures 3–5 show that the proposed methods with movable anchor node and unmovable anchor node have better performance in the error than others on the whole with the same condition.


### 4.2. Simulation for the Proposed Method with Different Numbers of Moveable Anchor Nodes

In this section, we suppose that the number of anchor nodes is 10 and different communication radiuses are 30, 40, 50, 60, and 70 meters. We change the number of movable anchor nodes to test the performance of the proposed method. Figure6 shows the average relative error of the proposed method with moveable anchor node for different number of movable anchor nodes and communication radius. From Figure 6, we can see that the average relative error reduces with the increase of the number of movable anchor nodes for the same communication radius and average relative error reduces with the increase of communication radius for the same number of movable anchor nodes.Figure 6
Average relative error of the proposed method with different number of movable anchor nodes and communication radius.


## 4.1. Only One Anchor Node Can Move for the Proposed Method with Moveable Anchor Node

In this section, the number of moveable anchor nodes is only one node for the proposed method with moveable anchor node. For example, if the number of anchor nodes is 10, then the moveable anchor node is 1 and the unmovable anchor node is 9 in the proposed method with moveable anchor node. Figure1 shows the relationship between the relative error and number of simulations with the condition that the number of anchor nodes is 10 and the maximum communication distance is 50 meters. From Figure 1, we can see that the proposed method with movable anchor node has the smallest relative error, and the next are the proposed method with unmovable anchor node and the method proposed in [19], respectively. The method proposed in [21] has the biggest relative error, and next is the method in [20]. Figure 2 shows the relationship between the average relative error and communication radius with the condition that the number of anchor nodes is 10 and the number of simulations is 10000. From Figure 2, we can see that the proposed method with movable anchor node has the smallest relative error, and the next is the proposed method with the unmovable anchor node for the different communication radius. The method proposed in [21] still has the biggest relative error, and next is the proposed method in [19, 20], respectively. Based on Figures 1 and 2, they show that the two proposed methods still have better performance in error than the proposed methods in [19–21] in different number of simulations and communication radius.Figure 1
The relative error with different number of simulations.Figure 2
The average relative error with different communication radius.Figures3–5 show the average relative error with different number of anchor nodes and maximum communication radius. The maximum communication radius is 30 m, 50 m, and 70 m for Figures 3–5, respectively. The number of simulations is 10000 times. From Figures 3–5, we can see that the average relative errors of all methods reduce with the increasing of the number of anchor nodes for the same communication radius. In Figure 3, the proposed method with movable anchor node has the smallest average relative error, and the next is, respectively, the proposed method with unmovable anchor node. Although the proposed method in [19] has the bigger average relative error than the proposed method in [20] when the number of anchor nodes is 4, it has smaller average relative error than the proposed method in [20] for other different numbers of anchor nodes. On the whole, the proposed method in [19] has the smaller average relative error than other proposed methods in [20, 21].Figure 3
The average relative error with different number of anchor nodes and communication radius 30 meters.Figure 4
The average relative error with different number of anchor nodes and communication radius 50 meters.Figure 5
The average relative error with different number of anchor nodes and communication radius 70 meters.In Figure4, our two proposed methods still have the smaller error than others. The proposed method in [21] has the biggest error; next is, respectively, the proposed method in [19, 20]. In Figure 5, when the number of anchor nodes is less than 4, the proposed method with unmovable node has the highest relative average error, and when the number of anchor nodes is more than 4, the proposed method with unmovable node has smaller average relative error than others except for the proposed method with movable anchor node. Although the proposed method in [19] has bigger error than method in [20] when the number of anchor nodes is less than 4, it has smaller error than method in [20] for other different numbers of anchor nodes. On the whole, the proposed method in [21] has biggest error; next is the method in [19, 20]. Therefore, Figures 3–5 show that the proposed methods with movable anchor node and unmovable anchor node have better performance in the error than others on the whole with the same condition.


## 4.2. Simulation for the Proposed Method with Different Numbers of Moveable Anchor Nodes

In this section, we suppose that the number of anchor nodes is 10 and different communication radiuses are 30, 40, 50, 60, and 70 meters. We change the number of movable anchor nodes to test the performance of the proposed method. Figure6 shows the average relative error of the proposed method with moveable anchor node for different number of movable anchor nodes and communication radius. From Figure 6, we can see that the average relative error reduces with the increase of the number of movable anchor nodes for the same communication radius and average relative error reduces with the increase of communication radius for the same number of movable anchor nodes.Figure 6
Average relative error of the proposed method with different number of movable anchor nodes and communication radius.


## 5. Conclusions

In this paper, we propose a location algorithm based on DV-Hop algorithm to improve the location accuracy of unknown node. The different numbers of anchor nodes and different communication radius are used to test the performance of the proposed method. We also suppose that all anchor nodes cannot move based on the proposed method with movable anchor node to construct a method named the proposed method with unmovable anchor node. The two methods have better performance in error than other methods in the same condition for different communication radius and number of anchor nodes. The proposed method with movable anchor node has the best performance in error than other methods.



---

*Source: 9275603-2020-08-01.xml*