Multihop Range-Free Localization with Virtual Hole Construction in Anisotropic Sensor Networks

Sang‐Woo Lee, Sunwoo KimThe Journal of Korean Institute of Communications and Information Sciences 2013 · DOI

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:

  1. 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."
  2. 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.
  3. 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.
Geometric model of the virtual hole construction.

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.
Network topologies used for simulation: Regular, C-shaped, and O-shaped.

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

Abstract

본 논문에서는 비등방성 센서 네트워크에서 노드 간 연결 정보만을 이용하여 일반노드의 위치를 찾는 다중 홉 Range-free 측위 알고리즘을 제안한다. 제안하는 측위 알고리즘에서 일반노드는 자신과 앵커노드 쌍이 이루는 최단경로의 측정 홉 수와 기대 홉 수를 비교하여 최단경로의 우회 정도를 측정하고, 우회 정도에 따라 자신으로부터 앵커노드까지의 거리를 추정한다. 일반노드는 이러한 과정을 네트워크의 모든 앵커노드 쌍에 대하여 반복하며, 획득한 거리 정보를 사용하여 위치를 추정한다. 제안하는 알고리즘은 기존의 Range-free 알고리즘에 비해 적은 수의 앵커노드를 필요로 하며, 적은 통신 오버헤드를 갖는다. 마지막으로 성능평가를 위하여 MATLAB 시뮬레이션을 수행하였으며, 기존의 Range-free 측위 알고리즘에 비해 향상된 위치정확도를 보였다. 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 MATLA simulations.
BibTeX
@article{lee2013multihop,
  author = {Sang‐Woo Lee and Sunwoo Kim},
  title = {{Multihop Range-Free Localization with Virtual Hole Construction in Anisotropic Sensor Networks}},
  journal = {The Journal of Korean Institute of Communications and Information Sciences},
  year = {2013},
  doi = {10.7840/kics.2013.38c.1.33},
}
Figure