Intelligent Drone Surveillance with Efficient Charging Mechanism Using Eternal Vertex Cover and p-Dispersion

Drones, or unmanned aerial vehicles (UAVs), are revolutionizing surveillance strategies across various sectors, including border security, wildlife conservation, and crowd management. Their real-time monitoring capabilities make them invaluable in challenging environments where traditional methods fall short. Along international borders and wildlife reserves, issues like illegal crossings, cattle smuggling, and poaching pose significant security and economic threats. Drones offer a cost-effective, flexible, and highly deployable solution, overcoming the limitations of static systems and human patrolling. This article presents a comprehensive framework for designing an efficient drone-based surveillance system by modeling the problem as the Eternal Vertex Cover (EVC) problem. To address the critical challenges of minimizing the number of drones required for complete coverage and managing their energy constraints, we propose a greedy heuristic EVC algorithm, along with two novel drone battery management strategies: Periodic Movements and Charging (PMC) and Periodic Movements and Charging with p-Dispersion (PMCD). The PMC strategy designates certain vertices of the input graph as charging stations randomly. In contrast, the PMCD strategy leverages the p-dispersion problem to optimize the spatial placement of charging stations, ensuring well-distributed coverage and reducing energy consumption. We evaluate the proposed algorithms extensively using randomly generated and benchmark datasets, with graph sizes varying between 25–100 vertices and 25–1000 edges. The results obtained show that the proposed approaches offer adversary-resistant, energy-fault-tolerant, and topology-adaptive solutions for large-scale surveillance, maintaining coverage even under targeted attacks.