Energy-Aware Eternal Vertex Cover for UAV-Based Surveillance Under Adversarial Edge Attacks

Persistent surveillance with Unmanned Aerial Vehicles (UAVs) is a key enabler for security-sensitive applications such as infrastructure protection and area monitoring. When the environment is abstracted as a network of Points of Interest (PoIs), defending connections against adversarial attacks naturally maps to the Eternal Vertex Cover (EVC) game, which provides a formal guarantee of continuous protection under an adaptive attacker. However, classical EVC formulations neglect operational constraints inherent to UAVs, like limited onboard energy and the need for periodic recharging-constraints that can be exploited to induce denial-of-surveillance conditions. In this paper, we study an energy-aware variant of EVC in which drones are subject to battery constraints and may recharge at designated charging stations, called Eternal Vertex Cover with Charging Stations (EVCCS). We propose Integer Linear Program (ILP) formulations that compute one-step defender reactions for both problems, and, to improve scalability, we also introduce lightweight solutions. Numerical results on random instances show that the ILP-based approaches significantly reduce the number of required drones compared to the sub-optimal solutions, and highlight how energy constraints and recharging affect the resilience of defensive strategies.