Combined Barrier-Target Coverage for Directional Sensor Network.

Area of Science:

• Computer Science
• Network Engineering
• Robotics

Background:

• Camera networks are widely used, necessitating advanced coverage strategies.
• Existing models like area, trap, barrier, and target coverage address specific network demands.
• There's a need for integrated approaches that simultaneously handle multiple coverage objectives.

Purpose of the Study:

• Define and address the novel Maximum Target Coverage with k-Barrier Coverage (MTCBC-k) problem.
• Develop efficient algorithms for solving the MTCBC-k problem in dynamic environments.
• Propose methods that outperform independent task optimization and merging.

Main Methods:

• Formulated the MTCBC-k problem using Integer Linear Programming (ILP).
• Developed two camera clustering techniques to decompose the problem into smaller ILPs.
• Introduced a polynomial-time greedy algorithm for efficient MTCBC-k problem solving.
• Adapted methods for scenarios with partial target detection.

Main Results:

• The proposed ILP formulation provides a baseline for MTCBC-k problem optimization.
• Clustering methods enable solving smaller, manageable ILPs and combining solutions effectively.
• The greedy algorithm offers a computationally efficient alternative for MTCBC-k problem resolution.
• Simulations demonstrated the effectiveness of clustering and greedy approaches under dense and sparse camera placements.

Conclusions:

• The MTCBC-k problem presents a new challenge in camera network coverage.
• Clustering and greedy algorithms offer practical and efficient solutions for MTCBC-k.
• The developed methods are valuable for real-world applications requiring simultaneous target and barrier coverage.