Node Scheduling Strategies for Achieving Full-View Area Coverage in Camera Sensor Networks

Peng-Fei Wu, Fu Xiao, Chao Sha, Haiping Huang, Ruchuan Wang, Naixue Xiong

TL;DR

This paper tackles the challenge of ensuring complete visual coverage in camera sensor networks (CSNs) by proposing a "full-view coverage" model. They introduce two novel algorithms, DPA for deterministic deployments and LNSA for random deployments, which efficiently select the minimum number of sensors to guarantee that any object within a region of interest can be captured from all its possible viewing angles.

What Problem Does This Paper Address?

Traditional wireless sensor networks (WSNs) often rely on scalar sensors that detect simple presence or measurements. However, modern applications demand richer information, leading to the development of wireless multimedia sensor networks (WMSNs), particularly camera sensor networks (CSNs). A key challenge in CSNs is ensuring effective "coverage," which goes beyond simply detecting an object's presence. For applications like intruder detection or surveillance, it's crucial to not only detect an object but also capture its appearance from all possible directions – its "face direction." This is known as "full-view coverage."

The problem is that camera sensors have a limited field of view and a specific sensing direction. Ensuring that an object, regardless of how it's oriented, is always captured by at least one sensor, and that sensor's view is sufficiently aligned with the object's orientation, is a complex optimization problem. Specifically, the paper addresses the "Full-View Area Coverage with Minimum number of sensors" (FACM) problem, which is known to be NP-hard. Existing approaches often struggle with efficiently determining the optimal sensor placement and orientation, especially in scenarios with random deployments.

Methods

The authors propose a novel "full-view coverage" model that considers both the sensor's sensing range and its viewing direction relative to the target's orientation. They derive the necessary and sufficient conditions for achieving full-view coverage for a single point.

Two primary algorithms are introduced:

  • Deployment Pattern Algorithm (DPA): This algorithm is designed for deterministic deployment, where sensor locations are pre-planned. DPA leverages a virtual grid (specifically, a triangle lattice) and calculates an optimal grid length. It then strategically deploys sensors around these virtual grid points, ensuring that the full-view coverage is achieved with a minimal number of nodes. The core idea is to "seamlessly stitch" regular hexagons formed by the virtual grid to approximate full-view area coverage.
  • Local Neighbor-optimal Selecting Algorithm (LNSA): This algorithm is tailored for random deployment, where sensors are placed without precise prior planning. LNSA aims to reduce redundancy by selecting a minimal subset of active sensors from a potentially larger, randomly distributed set. It refines the set of candidate sensors based on their proximity to critical trajectories and then selects nodes at specific intervals (20 degrees) to ensure full-view coverage. This algorithm also incorporates a form of "sleep scheduling" by implicitly selecting active nodes.

Datasets

Not discussed in the paper. The evaluation is based on simulations.

Key Insights and Ideas

  • The "Full-View Coverage" Concept: Moving beyond simple area coverage, this paper emphasizes the importance of capturing an object's orientation, which is critical for many surveillance and recognition tasks.
  • Geometric Approach to Coverage: The authors use geometric analysis, particularly focusing on hexagonal tessellations and sector-based coverage, to derive precise conditions for full-view coverage.
  • Bridging Point and Area Coverage: A key insight is that by ensuring full-view coverage for points within a virtual grid, approximate full-view area coverage can be achieved.
  • Deterministic vs. Random Deployment Strategies: The paper acknowledges that different deployment scenarios require distinct algorithmic approaches, leading to the development of both DPA and LNSA.
  • Optimizing Sensor Density: Both algorithms are designed to minimize the number of sensors required, which is crucial for reducing cost and power consumption in large-scale sensor networks.

Key Results

The paper presents simulation results demonstrating the effectiveness of their proposed algorithms.

  • DPA Performance: Simulations show that DPA requires a strictly smaller number of sensors compared to a baseline algorithm (FURCA) for achieving full-view area coverage in deterministic deployments. This improvement is attributed to DPA's more specific conditions for determining the optimal grid length.
  • LNSA Performance: LNSA demonstrates a faster convergence rate and requires fewer selected sensors compared to other algorithms (FURCA and DASH) in random deployment scenarios. This is attributed to LNSA's ability to adjust sensor working directions and schedule sleeping nodes effectively.
  • Parameter Impact: The simulations also illustrate how factors like sensing radius, angle of view, and effective angle influence the number of sensors needed for full-view coverage. Generally, a larger sensing radius and wider angles reduce the required sensor count.

Limitations and Future Work

  • Homogeneous Sensors: The current model assumes homogeneous camera sensors (same sensing radius, angle of view). Future work could explore heterogeneous sensor networks.
  • Idealized Environment: The analysis assumes an environment without obstacles. Real-world deployments would need to account for occlusions.
  • Specific Applications: While the algorithms are general, their verification for specific applications (e.g., maritime surveillance, intruder tracking) is suggested as future work.
  • Model Improvement: The authors suggest further research could focus on improving the sensing model itself and more rigorously verifying the algorithms in practical scenarios.

Summary updated

Abstract

Unlike conventional scalar sensors, camera sensors at different positions can capture a variety of views of an object. Based on this intrinsic property, a novel model called full-view coverage was proposed. We study the problem that how to select the minimum number of sensors to guarantee the full-view coverage for the given region of interest (ROI). To tackle this issue, we derive the constraint condition of the sensor positions for full-view neighborhood coverage with the minimum number of nodes around the point. Next, we prove that the full-view area coverage can be approximately guaranteed, as long as the regular hexagons decided by the virtual grid are seamlessly stitched. Then we present two solutions for camera sensor networks in two different deployment strategies. By computing the theoretically optimal length of the virtual grids, we put forward the deployment pattern algorithm (DPA) in the deterministic implementation. To reduce the redundancy in random deployment, we come up with a local neighboring-optimal selection algorithm (LNSA) for achieving the full-view coverage. Finally, extensive simulation results show the feasibility of our proposed solutions.
BibTeX
@inproceedings{wu2017node,
  author = {Peng-Fei Wu and Fu Xiao and Chao Sha and Haiping Huang and Ruchuan Wang and Naixue Xiong},
  title = {{Node Scheduling Strategies for Achieving Full-View Area Coverage in Camera Sensor Networks}},
  booktitle = {Sensors},
  year = {2017},
  url = {https://openreview.net/forum?id=i_uIB2FqFGi},
}
Figure