Liquan Zhao* and Kexin Zhang*
Localization Algorithm for Wireless Sensor Networks Based on Modified Distance Estimation
Abstract: The distance vector-hop wireless sensor node location method is one of typical range-free location methods. In distance vector-hop location method, if a wireless node A can directly communicate with wireless sensor network nodes B and C at its communication range, the hop count from wireless sensor nodes A to B is considered to be the same as that form wireless sensor nodes A to C. However, the real distance between wireless sensor nodes A and B may be dissimilar to that between wireless sensor nodes A and C. Therefore, there may be a discrepancy between the real distance and the estimated hop count distance, and this will affect wireless sensor node location error of distance vector-hop method. To overcome this problem, it proposes a wireless sensor network node location method by modifying the method of distance estimation in the distance vector-hop method. Firstly, we set three different communication powers for each node. Different hop counts correspond to different communi-cation powers; and so this makes the corresponding relationship between the real distance and hop count more accurate, and also reduces the distance error between the real and estimated distance in wireless sensor network. Secondly, distance difference between the estimated distance between wireless sensor network anchor nodes and their corresponding real distance is computed. The average value of distance errors that is computed in the second step is used to modify the estimated distance from the wireless sensor network anchor node to the unknown sensor node. The improved node location method has smaller node location error than the distance vector-hop algorithm and other improved location methods, which is proved by simulations.
Keywords: Communication Power , Distance Vector Hop Algorithm , Location Accuracy , Wireless Sensor Networks
1. Introduction
The wireless sensor networks (WSNs) has been applied in many fields [1-4], including industrial monitoring systems, environment monitoring, and smart home devices, etc. WSNs consists of nodes, which can communicate with each other for so long as one node is within another node’s communication range. The nodes in WSN can be divided two types: one is the anchor node, which has the global positioning system; its position information is known, whereas the positions of WSN unknown nodes have to be determined. Position information of each node is essential in surveillance, geographic environmental monitoring, geographic environmental monitoring, traffic condition monitoring, and patient tracking in healthcare. If the position of the node is unknown, the information it sends is useless.
There are two node location methods for WSNs: the range-based node location method and range-free node location method [5,6]. The range-based node location algorithm for WSNs requires the real physical information, such as angle or distance. It has a smaller location error, but it is easily affected by physical barriers; and so there is a need for additional devices that gather physical information. The range-free algorithm uses the relationship between nodes to locate unknown node positions. It has lower requirements in terms of node hardware compared to the range-based algorithm. This article mainly concerns the use of a range-free node location method to accurately determine the position information of unknown WSN nodes.
In recent years, a great many of range-based node location methods are introduced in WSN research. Examples include time of arrival node location method for WSNs [7,8], time difference of arrival node location method [9], angle of arrival node location method [10], etc. Although these algorithms have higher location accuracy, they need additional equipment for measuring the angle or distance, which in turn will consume energy and reduce the working lifetime of each node. Therefore, the range-based WSN node location method is only useful for specialized applications.
The range-free node location method only requires gathering information from anchor nodes to determine the relationships between anchor nodes and WSN unknown nodes to estimate the position of WSN unknown nodes. It does not require any additional equipment, and so it consumes less energy, thus increasing the working lifetime of each node. The range-free algorithm is therefore suitable for a wider range of applications compared with the other method. Typical range-free algorithm-based methods include Centroid location method for WSNs [11], approximate point in triangulation test (APIT) node location method [12], and distance vector-hop (DV-Hop) location method [13]. The Centroid method utilizes the mean value of coordinates for WSN anchor nodes and surrounding unknown sensor nodes to estimate their positions; however, this method has a larger error associated with estimating unknown node location. The node location method that is based on APIT uses anchor nodes to form a triangle; if an unknown node is located within the triangular area, its position relative to each anchor node coordinate is recorded, and the average anchor node coordinates are used in the location of unknown sensor node. The method has better performance than Centroid, but the location error is also larger.
The DV-Hop method is a typical range-free location method, which utilizes the hop count between wireless sensor anchor nodes and unknown sensor node as well as real physical information in order to determine the unknown node location; this method has a lower complexity. Based on the research of DV-Hop algorithm, many improved methods have been proposed in recent years. For example, Sheng and Zhang [14] improved the accuracy of estimated distances between WSN nodes by modifying the average distance per hop. Yang and Zhang [15] proposed dividing node communication power into several parts in an effort to determine the hop count more accurately, and they modified the average distance per hop in an effort to reduce location error. However, their method has lower location accuracy than that of the DV-Hop method. Fang et al. [16] proposed a node location method by modifying the hop count between anchor nodes and wireless sensor unknown nodes.
To further more reduce the location error, we improve the DV-Hop method by decreasing the error associated with location, and the error between the real distance and hop count. In this section, we have introduced the main WSN methods and briefly reviewed recent developments in the field. In Section 2, original DV-Hop location method is introduced. In Section 3, it analyzes the DV-Hop method, and introduces the improved DV-Hop algorithm for reducing location error. In Section 4, our simulations are provided and analyzed. Our findings are summarized in the last section.
2. Distance Vector-Hop Algorithm
It supposed that all sensor nodes are randomly employed in the whole workspace. The anchor nodes are accounted for using the global positioning system, which determines their coordinate information. The DV-Hop method utilizes the hop counts between each unknown node and other WSN anchor nodes in its gathering of real physical information. The principle of the DV-Hop algorithm proceeds as follows:
First step: Information is broadcasted to all WSN nodes by anchor nodes within their communication range. The information includes coordinates, node identification, and hop count (we set the value at 0 when it broadcasts). If a node receives the information, it updates the information by increasing the hop count (to 1), and then broadcasts the updated information. Therefore, an anchor node will receive dif¬ferent information that comes from the same anchor node via different routes. The different information contains many hop counts. Therefore, the hop count between different anchors can be obtained. The WSN anchor node uses the (1) to compute the average distance of per hop. That is
(1)
[TeX:] $$h o p_{i}=\frac{\sum_{j \neq i} \sqrt{\left(x_{i}-x_{j}\right)^{2}+\left(y_{i}-y_{j}\right)^{2}}}{\sum_{j \neq i} h_{i, j}}$$where [TeX:] $$h_{i, j}$$ is minimum value of hop count from sensor anchor node i to sensor anchor node [TeX:] $$j,\left(x_{i}, y_{i}\right)$$ is WSN anchor node i position coordinate, [TeX:] $$\left(x_{j}, y_{j}\right)$$ is the WSN anchor node j position coordinate, [TeX:] $$\text { hop }_{i}$$ is the average distance per hop of WSN anchor node i.
Second step: Calculating the estimation distance from an unknown sensor node to other sensor anchors is performed as follows:
where [TeX:] $$d_{i, k}$$ is the computed distance form unknown sensor node i to sensor anchor node k; [TeX:] $$\text { hop }_{i}$$ is unknown sensor node i (the mean distance per hop); and [TeX:] $$\text { chop }_{i, k}$$ is the hop count from unknown sensor node i and sensor anchor node k.
Final step: An unknown sensor node utilizes the received information from anchor nodes that are around itself and least squares method to realize location. The execution of the DV-Hop method is completed.
3. Improved Distance Vector-Hop Algorithm
In our proposed DV-Hop method, it uses the hop count from normal sensor node to anchor node, and the distance corresponding to hop count to estimate the distance from normal sensor node to WSNs anchor node. In the WSNs node communication range, the hop count between two sensor nodes that are is 1. The distance corresponding to hop count is the maximum communication distance, that is, the radius of communication range. We define the maximum radius as R. The real distance from sensor node A to sensor node B equals R, and the real distance between from sensor node A to sensor node C equals 0.2R. For sensor node A to sensor node B, node A to node C are positioned within the maximum range, so, using the DV-Hop method, the hop count we obtain from wireless node A to wireless node B is the same as that from wireless node A to wireless node C. Therefore, the estimated distance from wireless node A to wireless node B is the same as that from wireless node A to wireless node C. However, the real distance that is from wireless node A to wireless node B is actually different from the distance that is from wireless node A to node C. Location is mainly based on estimated distance of nodes, so error of estimated distance directly affects the location accuracy.
To overcome this problem, we can improve the DV-Hop algorithm by adjusting communication power, and by modifying the method of estimating mean distance per hop. Firstly, three different communication powers are set for all WSN nodes. The different communication powers have different communication ranges, and different communication ranges correspond to different hop counts. We define the maximum range as R. The three different maximum communication distances corresponding to four different communication powers are 0.3R, 0.6R, and 0.9R. If the maximum value of communication distance between two nodes in WSNs is 0.3R, the hop count between two wireless nodes in the range of maximum communication range is 0.2. If maximum value of communication range equals 0.6R, the hop count of two WSN nodes equals 0.5 within the range of the maximum communication range. If the maximum value of communication range is 0.9R, the hop count of two WSN nodes equals 0.8 within the range of the maximum communication radius.
Secondly, we compute the hop counts from the sensor anchor nodes to sensor unknown node. The information (that includes power information, coordinates, node identification and hop count) is broadcasted to the networks sequentially using the three different powers by WSN anchor nodes, which range from the minimum power to maximum power. The unknown nodes obtain the information, update the hop counts, and then transmit the updated information within the network using the different powers. The hop count is not always expressed in the form of an integer; however, this method can be used to obtain a more accurate hop count from one node to other node in WSNs.
Thirdly, the mean distance per hop [TeX:] $$\left(h o p_{j}\right)$$ is computed by using Eq. (1) for anchor node and Eq. (2) is used to compute the estimated distance from one sensor anchor node to the other sensor anchor nodes. In order to do this, we must already know the position information of the sensor anchor node, and so we can use real physical position-related information to calculate the real distance between each WSN anchor. The average error distance from the real distance for each WSN anchor node to estimated distance from each anchor node is expressed as:
where n denotes the number of WSN anchor nodes, [TeX:] $$D r_{i, j} \text { and } D e_{i, j}$$ denote the real distance and the estimated distance from anchor node i to all other WSN anchor nodes, [TeX:] $$E_{i}$$ is the mean error distance from one anchor node i to the other anchor nodes.
Finally, we compute the mean distance per hop for unknown nodes. Each unknown node will receive the mean distance of per hop from three sensor anchor nodes. They are the sensor nodes nearest to the WSN unknown node. We use these three mean distances from the WSN unknown node to the three anchor nodes nearest to the unknown node to estimate the mean distance per hop for unknown node as follows:
(4)
[TeX:] $$\text { Ahop }_{i}=\frac{\sum_{j=1}^{3} h_{i, j} \times h o p_{j}}{\sum_{j=1}^{3} h_{i, j}}$$whereby [TeX:] $$h_{i, j}$$ is hop count from unknown node i to one of the nearest three wireless sensor anchor j, [TeX:] $$\text { Ahop }_{i}$$ is the modified mean distance per hop for WSN unknown node i, [TeX:] $$\text { hop }_{j}$$ is the mean distance per hop of wireless anchor node j. Based on Eq. (4) and hop count from wireless unknown node i to anchor node j, we can obtain the estimated distance from unknown sensor node i to sensor anchor node j as follows:
To further reduce the distance error, we use Eq. (3) to modify Eq. (5):
where [TeX:] $$D_{m i, j}$$ is the modified estimation distance from sensor anchor node j to unknown sensor node i, [TeX:] $$D_{e i, j}$$ denotes estimation distance from unknown node i to WSN anchor node j, [TeX:] $$\text { Ahop }_{i}$$ denotes average distance per hop for wireless unknown sensor node i, and denotes the adjustment factor, set to [TeX:] $$\beta=1 / R$$ (R is maximum value of communication range for wireless network nodes).
The relationship between the coordinates of each node and estimated distance is given as follows [17]:
(7)
[TeX:] $$\left\{\begin{array}{l} D_{m i, 1}^{2}=\left(x_{i}-x_{1}\right)^{2}+\left(y_{i}-y_{1}\right)^{2} \\ D_{m i, 2}^{2}=\left(x_{i}-x_{2}\right)^{2}+\left(y_{i}-y_{2}\right)^{2} \\ L \\ D_{m i, j}^{2}=\left(x_{i}-x_{j}\right)^{2}+\left(y_{i}-y_{j}\right)^{2} \end{array}\right.$$where denotes computed distance from WSN unknown node i to all WSN anchor nodes [TeX:] $$j ;\left(x_{j}, y_{j}\right)$$ is the position coordinate of WSN anchor node j; and [TeX:] $$\left(x_{i}, y_{i}\right)$$ is the estimation coordinates for WSN unknown node i. Using Eq. (7), we can get:
(8)
[TeX:] $$\left\{\begin{array}{l} x_{1}^{2}-x_{j}^{2}-2\left(x_{1}-x_{j}\right) x_{i}+y_{1}^{2}-y_{j}^{2}-2\left(y_{1}-y_{j}\right) y_{i}=D_{m i, 1}^{2}-D_{m i, j}^{2} \\ x_{2}^{2}-x_{j}^{2}-2\left(x_{2}-x_{j}\right) x_{i}+y_{2}^{2}-y_{j}^{2}-2\left(y_{2}-y_{j}\right) y_{i}=D_{m i, 2}^{2}-D_{m i, j}^{2} \\ L \\ x_{j-1}^{2}-x_{j}^{2}-2\left(x_{j-1}-x_{j}\right) x_{i}+y_{j-1}^{2}-y_{j}^{2}-2\left(y_{j-1}-y_{j}\right) y_{i}=D_{m i,(j-1)}^{2}-D_{m i, j}^{2} \end{array}\right.$$We express Eq. (8) as a matrix, which represents:
We state that [TeX:] $$X=\left[x_{i}, y_{i}\right]^{T},$$ which in turn are the coordinates of the estimated position that are used to determine the value of WSN unknown node i. Thus,
(10)
[TeX:] $$A=2 \times\left(\begin{array}{cc} \left(x_{1}-x_{j}\right) & \left(y_{1}-y_{j}\right) \\ \left(x_{2}-x_{j}\right) & \left(y_{2}-y_{j}\right) \\ \mathrm{~L} & \mathrm{~L} \\ \left(x_{j-1}-x_{j}\right) & \left(y_{j-1}-y_{j}\right) \end{array}\right)$$
(11)
[TeX:] $$B=\left[\begin{array}{l} x_{1}^{2}-x_{j}^{2}+y_{1}^{2}-y_{j}^{2}+D_{m i, j}^{2}-D_{m i, 1}^{2} \\ x_{2}^{2}-x_{j}^{2}+y_{2}^{2}-y_{j}^{2}+D_{m i, j}^{2}-D_{m i, 2}^{2} \\ \mathrm{~L} \\ x_{j-1}^{2}-x_{j}^{2}+y_{j-1}^{2}-y_{j}^{2}+D_{m, j}^{2}-D_{m i,(j-1)}^{2} \end{array}\right]$$The position of WSN unknown node is estimated as follows:
4. Simulation and Discussion
We describe our simulation results for determining location, and performance of our simulation in this section. For our model, we assume that the workspace is square and that the length is m for each side. The initial number of the system equals 100. The maximum value of communication range for wireless network node is 50 m. The initial number of WSN anchor nodes equals 10. We use the average relative error to measure location error. It can be expressed as:
(13)
[TeX:] $$A r=\frac{1}{R} \sum_{i=1}^{n} \frac{\sqrt{\left(x_{r}-x_{i}\right)^{2}+\left(y_{r}-y_{i}\right)^{2}}}{n}$$where n denotes the number of wireless network unknown nodes, [TeX:] $$\left(x_{r}, y_{r}\right)$$ denote the real position for WSN unknown node i, R denotes the maximum value of communication range radius, [TeX:] $$\left(x_{i}, y_{i}\right)$$ denote the estimated position of WSN unknown node i. In ideal case, the real position is the same as estimated position for an unknown node, and the average relative location error is equal to zero. The smaller the average relative location error in WSN, the smaller the location error is and the better the performance in location detection. Therefore, we use Eq. (13) to measure the location error of WSN location methods for unknown sensor node.
In our simulation, our proposed method is compared with the IDV-Hop algorithm [14], weighted DV-Hop [15] and another improved DV-Hop algorithm [16]. The number of WSN anchor nodes equals 10, and each method has only been run once. The distance difference between the real distance and estimated distance for different methods are shown in Fig. 1. The distance error of our proposed method is smaller than other methods for some unknown nodes, and is larger than those of some other algorithms for some unknown nodes. Our improved location method has smaller location error than other wireless sensor location methods accounting for most of the unknown nodes.
To further examine the error, we can determine the average relative location error as specified in Eq. (13). The average relative location errors for the four different methods are shown in Table 1. The average relative location errors for our proposed method, IDV-Hop algorithm [14], weighted DV-Hop [15], and the other improved DV-Hop algorithm [16] are 0.0993, 0.2016, 0.1195, and 0.1302, respectively. Our proposed method has the smallest average relative location error, followed by that for the weighted DV-Hop method [15]. In Fig. 2, the average location error for different location algorithms across a running times range of 1,500 to 20,000 is shown. This shows that our proposed location method still has the smallest average relative location error compared with the other methods for different running times.
Fig. 1.
Table 1.
| Algorithm | Average relative location error |
|---|---|
| Shen and Zhang [14] | 0.2106 |
| Yang and Zhang [15] | 0.1195 |
| Fang et al. [16] | 0.1302 |
| Proposed method | 0.0993 |
We also ran simulations using different location methods with different settings for the communication range radius and the number of anchor nodes. The number of anchor nodes ranges from 7 to 15. The maximum communication radiuses are from 30 m to 50 m. The simulation results are shown in Figs. 3–7, respectively. Our proposed location method still has the smallest average relative location error, followed by that for the method specified in literature [15] with different number of anchor nodes. The average relative location error reduces with increasing communication range radius with the condition that the number of anchor nodes is constant. Based on above analysis, our improved sensor node location algorithm has the smallest location error for WSN comparing with these methods [14–16] with different conditions.
5. Conclusion
An improved DV-Hop p location method is introduced in this paper. We firstly set three different communication powers for all nodes so that each node can operate at different communication ranges.
We can therefore obtain different hop counts for different communication ranges between two nodes. For the purpose of hop count accuracy, we select the minimum value of hop count between wireless sensor nodes as final hop count. Secondly, we compute average value using three different average distances per hop from sensor node that the position is unknown to three wireless anchor nodes that are nearest to the unknown node; for this, the average value is used as the average distance of per hop for the unknown node. Finally, we use average differences between real distances among anchor nodes and estimated distances among anchor nodes in order to modify our estimates of the distance from the wireless anchor nodes to an unknown wireless node. In a comparative study of our proposed algorithm and three other location algorithms, we have shown that the error associated with our proposed algorithm is the smallest among the four methods.
References
- 1 D. Wang, W. Li, P. Wang, "Measuring two-factor authentication schemes for real-time data access in industrial wireless sensor networks," IEEE Transactions on Industrial Informatics, vol. 14, no. 9, pp. 4081-4092, 2018.doi:[[[10.1109/TII.2018.2834351]]]
- 2 N. Dey, A. S. Ashour, F. Shi, S. J. Fong, R. S. Sherratt, "Developing residential wireless sensor networks for ECG healthcare monitoring," IEEE Transactions on Consumer Electronics, vol. 63, no. 4, pp. 442-449, 2017.doi:[[[10.1109/TCE.2017.015063]]]
- 3 H. Zhu, Y. Li, "Distribution transformer monitoring system operating parameters and design," Journal of Northeast Electric Power University, vol. 38, no. 5, pp. 74-79, 2018.custom:[[[-]]]
- 4 C. Lin, H. Tong, W. Yu, Y. Xin, R. Zhang, "Distribution grid intelligent state monitoring and fault handling platform based on ubiquitous power Internet of Things," Journal of Northeast Electrical Power University, vol. 39, no. 4, pp. 1-4, 2019.custom:[[[-]]]
- 5 X. Liu, J. Yin, S. Zhang, B. Ding, S. Guo, K. Wang, "Range-based localization for sparse 3-D sensor networks," IEEE Internet of Things Journal, vol. 6, no. 1, pp. 753-764, 2019.custom:[[[-]]]
- 6 M. Singh, S. K. Bhoi, P. M. Khilar, "Geometric constraint-based range-free localization scheme for wireless sensor networks," IEEE Sensors Journal, vol. 17, no. 16, pp. 5350-5366, 2017.custom:[[[-]]]
- 7 X. Liang, H. Zhang, T. Lu, T. A. Gulliver, "Extreme learning machine for 60 GHz millimetre wave positioning," IET Communications, vol. 11, no. 4, pp. 483-489, 2017.doi:[[[10.1049/iet-com.2016.0080]]]
- 8 J. Cheon, H. Hwang, D. Kim, Y. Jung, "IEEE 802.15. 4 ZigBee-based time-of-arrival estimation for wireless sensor networks," Sensors, vol. 16, no. 203, 2016.custom:[[[-]]]
- 9 X. Liang, H. Zhang, T. Lu, T. A. Gulliver, "Energy detector based TOA estimation for MMW systems using machine learning," Telecommunication Systems, vol. 64, no. 2, pp. 417-427, 2017.doi:[[[10.1007/s11235-016-0182-2]]]
- 10 S. Tomic, M. Beko, R. Dinis, P. Montezuma, "A closed-form solution for RSS/AoA target localization by spherical coordinates conversion," IEEE Wireless Communications Letters, vol. 5, no. 6, pp. 680-683, 2016.doi:[[[10.1109/LWC.2016.2615614]]]
- 11 A. Stanoev, S. Filiposka, V. In, L. Kocarev, "Cooperative method for wireless sensor network localization," Ad Hoc Networks, vol. 40, pp. 61-72, 2016.doi:[[[10.1016/j.adhoc.2016.01.003]]]
- 12 L. Wang, P. Zhang, L. Wei, "A new DV-hop algorithm in wireless sensor network," in Proceedings of 2013 2nd International Symposium on Instrumentation and Measurement, Sensor Network and Automation (IMSNA), Toronto, Canada, 2013;pp. 194-197. custom:[[[-]]]
- 13 G. Li, S. Zhao, J. Wu, C. Li, Y. Liu, "DV-hop localization algorithm based on minimum mean square error in Internet of Things," Procedia Computer Science, vol. 147, pp. 458-462, 2019.custom:[[[-]]]
- 14 M. Shen, Y. Zhang, "DV -hop localization algorithm based on improved average hop distance and estimate of distance," Application Research of Computer, vol. 28, no. 2, pp. 648-650, 2011.custom:[[[-]]]
- 15 X. Yang, W. Zhang, "An improved DV-hop localization algorithm based on hop distance and hops correction," International Journal of Multimedia and Ubiquitous Engineering, vol. 11, no. 6, pp. 319-328, 2016.custom:[[[-]]]
- 16 W. Fang, Y. Hu, Z. Hu, "DV -HOP algorithm to reevaluate hop distance and amend minimum hop count," Journal of Electronic Measurement and Instrumentation, vol. 32, no. 8, pp. 201-208, 2018.custom:[[[-]]]
- 17 L. Cui, C. Xu, G. Li, Z. Ming, Y. Feng, N. Lu, "A high accurate localization algorithm with DV-Hop and differential evolution for wireless sensor network," Applied Soft Computing, vol. 68, pp. 39-52, 2018.doi:[[[10.1016/j.asoc.2018.03.036]]]