Enhancing Received Signal Strength-Based Localization through Coverage Hole Detection and Recovery

Shuangjiao Zhai, Zhanyong Tang, Dajin Wang, Qingpei Li, Zhanglei Li, Xiaojiang Chen, Dingyi Fang, Feng Chen, Zheng Wang

TL;DR

This paper addresses the critical issue of coverage holes in wireless sensor networks (WSNs) that use Received Signal Strength Indicator (RSSI) for localization. It proposes a novel algorithm that leverages Voronoi tessellation and Delaunay triangulation to effectively detect and recover these coverage gaps, enhancing the accuracy and reliability of RSSI-based localization systems.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are increasingly used for applications like environmental monitoring, intrusion detection, and wildlife tracking, where knowing the precise location of events or objects is crucial. Localization techniques, particularly those based on Received Signal Strength Indicator (RSSI), are vital for this. However, a fundamental challenge in WSNs is ensuring adequate "coverage," meaning that the entire target area is monitored by sensors. "Coverage holes" are areas not effectively covered by sensors, which can significantly degrade the performance of these applications.

Existing methods for detecting and recovering coverage holes often assume a simplified "disk" model for sensor coverage. This assumption is problematic because RSSI-based localization techniques, due to the nature of signal propagation and interference, often exhibit a non-disk, specifically an "ellipse," coverage model. This discrepancy means that traditional coverage hole solutions are not directly applicable to RSSI-based localization, leading to persistent coverage gaps even when existing methods claim full coverage. This paper tackles this gap by developing a method specifically for the ellipse coverage model inherent in RSSI localization.

Methods

The core of this paper's contribution lies in its novel algorithm for detecting and recovering coverage holes within the context of an ellipse coverage model. The approach is built upon two well-established geometric concepts:

  • Voronoi Tessellation: This technique partitions the target region into sub-regions, where each sub-region is closer to one specific sensor node than any other. This helps identify areas that are sparsely covered or potentially have coverage holes by highlighting the "sparsest" parts of the region.
  • Delaunay Triangulation: This is the dual of Voronoi tessellation. It connects sensor nodes to form triangles. Coverage holes are often found to exist within these triangles.

The algorithm proceeds in two main phases:

  1. Coverage Hole Detection: The paper first defines how to calculate the coverage rate. It models the target region as a grid of small square elements and determines if the center of each element is covered by at least one sensor's ellipse coverage. The coverage rate is then the ratio of covered square elements to the total number of elements. If this rate falls below a predefined threshold, coverage holes are identified.
  2. Coverage Hole Recovery: When coverage holes are detected, the algorithm proposes deploying additional sensors. The key innovation is determining optimal locations for these new sensors. The algorithm identifies the triangle with the largest area in the Delaunay triangulation (as coverage holes are often found within these).
  3. If the current coverage rate is below 90%, a new sensor is strategically placed at the circum-center of this largest triangle.
  4. If the coverage rate is between 90% and 100%, the new sensor is placed at the barycenter of the largest triangle.

This placement strategy aims to maximize the coverage increase with the minimum number of additional sensors, addressing the "Optimum Increase Coverage Problem" (OICP), which is proven to be NP-complete. The algorithm is iterative, recalculating coverage and adding sensors until the desired coverage rate is achieved.

Datasets

The paper does not explicitly mention or use pre-existing datasets for training or evaluation. Instead, it relies on simulation experiments conducted using MATLAB R2014a. The experimental setup involves a simulated 300x300 meter target region with sensor nodes having a transmission and sensing range of 100m and 50m respectively. The paper also includes experimental verification in an outdoor environment with physical sensor deployments to validate the ellipse coverage model.

Key Insights and Ideas

  • The Ellipse is Key: The most fundamental insight is that RSSI-based localization's coverage model is an ellipse, not a simple disk. This distinction is crucial because it means existing coverage hole solutions are insufficient.
  • Geometric Approach to Coverage: The paper elegantly applies Voronoi tessellation and Delaunay triangulation, standard tools in computational geometry, to a practical WSN problem. This demonstrates their power beyond theoretical applications.
  • Strategic Sensor Placement: The algorithm's core innovation is its intelligent placement of new sensors. By targeting the largest triangles in the Delaunay triangulation and choosing specific points (circum-center or barycenter) based on the current coverage level, it efficiently addresses coverage gaps.
  • OICP is NP-Complete: Proving that the problem of optimally increasing coverage with minimal new sensors is NP-complete highlights the inherent difficulty of this problem and justifies the need for an approximation algorithm.
  • Threshold-Based Placement: The use of a 90% coverage threshold to switch between placing sensors at the circum-center versus the barycenter is an empirical observation that leads to more efficient recovery.

Key Results

  • The proposed algorithm successfully detects and recovers coverage holes in WSNs with an ellipse coverage model.
  • Simulation results demonstrate that the algorithm can achieve any desired coverage rate, including 100% coverage.
  • The method is shown to be more efficient than existing disk-based coverage hole recovery methods, requiring fewer additional sensors to achieve comparable or better coverage. For instance, in one scenario, the proposed method needed 362 additional sensors to reach 100% coverage, while a prior method required 382 for the same goal.
  • Experimental verification supports the theoretical ellipse coverage model and shows that coverage holes in theory and experiment are similar.

Limitations and Future Work

  • Idealized Deployment: The current implementation assumes an ideal deployment scenario with regular shapes and no obstacles. The authors acknowledge that real-world environments are more complex, with irregular target regions, potential obstacles (like trees), and missed communication links.
  • 2D Plane Assumption: The work is limited to a 2-dimensional plane.
  • Single Target Object: The current approach assumes only one target object in the deployment area. Multi-object localization is noted as an open problem.

The authors suggest future work will focus on improving the algorithm by:

  • Considering irregular shapes of target regions.
  • Incorporating the impact of obstacles and borders.
  • Handling more complex deployment environments.
  • Extending to multi-object localization scenarios.

Summary updated

Abstract

In wireless sensor networks (WSNs), Radio Signal Strength Indicator (RSSI)-based localization techniques have been widely used in various applications, such as intrusion detection, battlefield surveillance, and animal monitoring. One fundamental performance measure in those applications is the sensing coverage of WSNs. Insufficient coverage will significantly reduce the effectiveness of the applications. However, most existing studies on coverage assume that the sensing range of a sensor node is a disk, and the disk coverage model is too simplistic for many localization techniques. Moreover, there are some localization techniques of WSNs whose coverage model is non-disk, such as RSSI-based localization techniques. In this paper, we focus on detecting and recovering coverage holes of WSNs to enhance RSSI-based localization techniques whose coverage model is an ellipse. We propose an algorithm inspired by Voronoi tessellation and Delaunay triangulation to detect and recover coverage holes. Simulation results show that our algorithm can recover all holes and can reach any set coverage rate, up to 100% coverage.
BibTeX
@inproceedings{zhai2018enhancing,
  author = {Shuangjiao Zhai and Zhanyong Tang and Dajin Wang and Qingpei Li and Zhanglei Li and Xiaojiang Chen and Dingyi Fang and Feng Chen and Zheng Wang},
  title = {{Enhancing Received Signal Strength-Based Localization through Coverage Hole Detection and Recovery}},
  booktitle = {Sensors},
  year = {2018},
  url = {https://openreview.net/forum?id=7mrOp3_tUs9},
}
Figure