Nowadays, Unmanned Aerial Vehicles (UAV) are frequently present in the civilian environment. However, proper implementations of different solutions based on these aircraft still face important challenges. This article deals with multi-UAV systems, forming aerial networks, mainly employed to provide Internet connectivity and different network services to ground users. However, the mission duration (hours) is longer than the limited UAVs' battery life-time (minutes). This paper introduces the UAV replacement procedure as a way to guarantee ground users' connectivity over time. This article also formulates the practical UAV replacements problem in moderately large multi-UAV swarms and proves it to be an NP-hard problem in which an optimal solution has exponential complexity. In this regard, the main objective of this article is to evaluate the suitability of heuristic approaches for different scenarios. This paper proposes betweenness centrality heuristic algorithm (BETA), a graph theory-based heuristic algorithm. BETA not only generates solutions close to the optimal (even with 99% similarity to the exact result) but also improves two ground-truth solutions, especially in low-resource scenarios.
Keywords: UAV; UAV fleet; UAV replacement; UAV swarm; algorithms; energy consumption; optimization; self-organization.