DV-Hop Localization Algorithm for Wireless Sensor Networks
Abstract: Based on distance vector and GPS positioning principles, in 2001, Nieuleseu et al. proposed the DV-Hop localization algorithm for sensor nodes, which only requires a few anchor nodes while the remaining nodes are unknown and need to determine their positions through the localization algorithm. This method does not require distance measurement and has low hardware requirements, making it widely used in Wireless Sensor Networks (WSN) with limited hardware conditions.
1. Algorithm Principle
The localization steps of the DV-Hop algorithm are as follows:
(1) Each anchor node broadcasts its location information to neighboring nodes within its communication range. The receiving nodes record the minimum hop count to each anchor node while ignoring larger hop count information from the same anchor node, and then increment the hop count by 1 before forwarding it to neighboring nodes.
(2) Each anchor node estimates the average hop distance of the network using the coordinates of other anchor nodes and the hop counts recorded, according to Equation (1). In this equation, represents the other anchor node numbers in the anchor node data table, and represents the hop count between the anchor node and.
After broadcasting the calculated average hop distance to the entire network, the unknown nodes only record the first received average hop distance and forward it to neighboring nodes. Upon receiving the average hop distance, the unknown node estimates the distance from node i to a certain anchor node based on the recorded hop count information, according to Equation (2):
(3) Let represent the coordinates of anchor nodes, and the position of the node D to be located is, with estimated distances to the anchor nodes being. This leads to the establishment of the equation in Equation (3). By subtracting the last equation from the first equation group, we obtain: represented as a linear equation group, where
The solution to the equation group is obtained using the least squares method:
2. Algorithm Testing
Set the node coverage area to 200×200, with a total of 200 nodes, 20 beacon nodes, a communication radius of 30, and 180 unknown nodes. The normalized average localization error is used as the evaluation index: where is the number of unknown nodes; is the number of experiments; is the communication radius of the nodes; is the estimated coordinates of the unknown nodes; is the true coordinates of the unknown nodes.
The normalized localization error of the basic DV-hop is: 0.5384
3. References
[1] Wu Xide, Fang Jie, Yang Shijie, Zhou Qingbiao. A Sensor Node Localization Method Based on GPSO-DVHop [J]. Computer Engineering and Applications, 2013, 49(22): 95-99.
[2] Zhang Heng. Research and Implementation of Wireless Sensor Node Localization Methods [D]. South China University of Technology, 2012.
4. Matlab Code
Click “Read the original text” to get it!