A Weighted Processing-Based Average Hop Distance Estimation Algorithm for Wireless Sensor Networks (W-DVHop)

Abstract: Positioning technology is one of the key technologies in wireless sensor networks. The traditional DV-Hop positioning algorithm only considers the average hop distance value estimated by the nearest anchor node, while the average hop distance value estimated by a single anchor node cannot accurately reflect the actual average hop distance of the network. This paper proposes a weighted processing-based average hop distance estimation algorithm that considers the average hop distance values estimated by multiple anchor nodes and weights them according to the number of hops to the unknown node, making the estimation of the network’s average hop distance more accurate.

1. Principles of the DV-Hop Algorithm

The DV-Hop algorithm consists of three stages. First, a typical distance vector exchange protocol is used to allow all nodes in the network to obtain the number of hops to the anchor nodes. In the second stage, after obtaining the positions and hop counts of other anchor nodes, the anchor nodes estimate the network’s average hop distance and broadcast it throughout the network. The average hop distance value is propagated in the network using a controlled flooding method, allowing nodes to only accept the values from the nearest anchor node. When the average hop distance value is received, the unknown node calculates the distance to the anchor node based on the number of hops to the anchor node. When the unknown node obtains distances to three or more anchor nodes, the third stage performs trilateration positioning.

1.1 Average Hop Distance Estimation Algorithm in DV-Hop

In the DV-Hop algorithm, the unknown node receives the average hop distance value estimated by the nearest anchor node as its own average hop distance value. The specific calculation of the average hop distance is as follows. The average hop distance estimated by the anchor node: where represents the distance and hop count between anchor nodes and , that is, the average hop distance value estimated by the anchor node equals the sum of distances between this anchor node and other anchor nodes divided by the sum of hop counts between this anchor node and other anchor nodes.

The unknown node takes the average hop distance estimated by the nearest anchor node as its own average hop distance value, that is, where is the average hop distance value of the unknown node, and is the average hop distance value estimated by the nearest anchor node to the unknown node. The unknown node then obtains its distance to each anchor node using the following formula.

2. Weighted Processing-Based Average Hop Distance Estimation Algorithm

The basic idea of the weighted processing-based average hop distance estimation algorithm is as follows: after the unknown node receives the average hop distance values from multiple anchor nodes, it normalizes and weights the average hop distance values estimated by each anchor node, assigning larger weights to closer anchor nodes. This design is mainly based on two considerations: (1) For the network, the average hop distance estimated by a single anchor node may have a significant deviation. If the unknown node uses this anchor node’s estimated value as its own average hop distance, it will result in lower positioning accuracy for that unknown node, thus affecting the overall positioning accuracy of the network. Therefore, it is necessary to comprehensively consider the average hop distances of multiple anchor nodes to estimate the average hop distance more accurately; (2) For an unknown node, different anchor nodes at varying distances reflect its local network state differently. Closer anchor nodes may more accurately reflect the actual average hop distance in their surrounding local network, thus requiring larger weights to be assigned to closer anchor nodes.

Next, we will specifically introduce the calculation methods for the weights of each anchor node and the average hop distance value of the unknown node in the new algorithm. For convenience, let the estimated average hop distance of anchor node be denoted as, and the hop count from the unknown node to anchor node be denoted as (where i=1,2,3…).

Assuming the unknown node receives information from anchor nodes, let the weighted value of the average hop distance of each anchor node be denoted as, then take which means the weight of anchor node i equals the reciprocal of the hop count from the unknown node to anchor node i divided by the sum of the reciprocals of the hop counts from the unknown node to all anchor nodes. This normalization process uses a uniform standard to handle each unknown node and ensures that the sum of the weights of all anchor nodes equals 1. At the same time, by assigning larger weights to closer anchor nodes, it distinguishes the degree to which anchor nodes at different distances reflect the actual average hop distance of the network.

Based on the average hop distance estimated by each anchor node, in the Weight-DV-Hop algorithm, the average hop distance of the unknown node is calculated as: that is, the average hop distance of the unknown node equals the sum of the products of the weighted values of each anchor node’s average hop distance and each anchor node’s average hop distance. In this way, the average hop distance values of each anchor node are weighted according to their distances from the unknown node, making the estimated average hop distance of the unknown node more accurate and better reflecting the actual average hop distance of the network.

Then, similar to the DV-Hop algorithm, the distance between the unknown node and the anchor nodes is calculated using equation (3). Compared to the DV-Hop positioning algorithm, the Weight-DV-Hop positioning algorithm only replaces the average hop distance estimated by the nearest anchor node to the unknown node with the weighted processing-based average hop distance, while the other processes remain the same.

3. Algorithm Testing

Set the node coverage area to 200×200, with a total of 200 nodes, 50 beacon nodes, a communication radius of 30, and 150 unknown nodes. The normalized average positioning 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 node; is the true coordinates of the unknown node.

The normalized positioning error of W-DV-Hop: 0.41648

4. References

[1] Liu Feng, Zhang Han, Yang Ji. A Weighted Processing-Based Average Hop Distance Estimation Algorithm for Wireless Sensor Networks [J]. Journal of Electronics and Information Technology, 2008(05):1222-1225.

5. Matlab Code

Click “Read the original text” to get it!