Abstract
This paper presents a multihop range-free localization algorithm to estimate the physical location of a normal node with local connectivity information in anisotropic sensor networks. In the proposed algorithm, a normal node captures the detour degree of the shortest path connecting an anchor pair and itself by comparing the measured hop count and the expected hop count, and the node estimates the distances to the anchors based on the detour degree. The normal node repeats this procedure with all anchor combinations and pinpoints its location using the obtained distance estimates. The proposed algorithm requires fewer anchors and less communication overhead compared to existing range-free algorithms. We showed the superiority of the proposed algorithm over existing range-free algorithms through MATLAB simulations.
Introduction
In Wireless Sensor Networks (WSNs), knowing the physical location of sensor nodes is critical for data sensing and routing. While GPS is an option, it is often too expensive or power-hungry for mass-deployed low-cost sensors. "Range-free" localization techniques are a popular alternative because they estimate positions using only connectivity information (who can talk to whom) rather than expensive distance-measuring hardware.
However, most standard range-free algorithms (like DV-Hop) assume an "isotropic" network—one where nodes are spread uniformly and signals travel in perfect circles. In the real world, obstacles, irregular terrain, or "holes" in the deployment force communication paths to detour. In these anisotropic networks, a high hop count doesn't necessarily mean a node is far away; it might just mean the signal had to go around a building. This leads to massive errors in position estimation.
Proposed Method: Virtual Hole Construction
The authors propose a Virtual Hole Construction approach to correct for these detours. The process works in three main stages:
- Detour Measurement: A normal node looks at a pair of anchor nodes (nodes with known locations). It calculates the "expected hop count" (what the count would be if the path were a straight line) and compares it to the "measured hop count." The difference between these two values defines the "detour degree."
- Virtual Hole Modeling: The algorithm assumes the detour is caused by a circular obstacle (a virtual hole). Using the detour degree, the node models the shortest path as an arc of a circle passing around this hole. By applying geometric formulas relating arc length to chord length, the node can estimate the true straight-line distance to the anchors.
- Location Pinpointing: The node repeats this process for various anchor combinations and then uses a Least Squares method to calculate its final coordinates based on the refined distance estimates.
What makes this novel is that it doesn't just try to "smooth" the hop count; it actively reconstructs the likely geometry of the path detour.
Experimental Setup
The researchers evaluated their algorithm using MATLAB simulations across three distinct terrain models to simulate real-world challenges:
- Regular: A standard uniform deployment.
- C-shaped: Simulates a large concave obstacle in the center.
- O-shaped: Simulates a "donut" deployment with a hole in the middle.
They also utilized the QUDG (Quasi Unit Disk Graph) model to account for radio irregularity (DOI - Degree of Irregularity), ensuring the simulation reflected unpredictable signal propagation.
Key Results
The proposed algorithm was compared against three benchmarks: DV-Hop, REP, and Pattern-driven localization.
- Accuracy: In the challenging C-shaped terrain, the proposed algorithm achieved a localization error of 1.113 $d_{tx}$, significantly outperforming REP (1.469) and DV-Hop (1.485).
- Consistency: As the number of hops increased, the error rate of the proposed algorithm stayed relatively flat or even improved, while other algorithms saw their errors spike.
- Overhead: The method requires only $O(AN)$ communication overhead (where $A$ is the number of anchors and $N$ is the number of nodes), which is lower than "hole-searching" algorithms like REP.
Conclusion
The Virtual Hole Construction algorithm offers a significant improvement in localization accuracy for anisotropic sensor networks. By treating detours as geometric properties, it achieves high precision with fewer anchor nodes and lower communication overhead. Future work may involve refining the virtual hole shape for non-circular obstacles or extending the model to 3D environments.
Summary updated