Sanchez-Aguero Victor, Valera Francisco, Vidal Ivan, Tipantuña Christian, Hesselbach Xavier
IMDEA Networks Institute, Avda. del Mar Mediterráneo, 22, 28918 Madrid, Spain.
Departamento de Ingeniería Telemática, Universidad Carlos III de Madrid, Avda. Universidad, 30, 28911 Leganés, Madrid, Spain.
Sensors (Basel). 2020 May 14;20(10):2791. doi: 10.3390/s20102791.
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.
如今，无人机（UAV）在民用环境中频繁出现。然而，基于这些飞行器的不同解决方案的恰当实施仍面临重大挑战。本文探讨了构成空中网络的多无人机系统，其主要用于为地面用户提供互联网连接和不同的网络服务。然而，任务持续时间（数小时）长于无人机有限的电池续航时间（数分钟）。本文引入无人机替换程序，作为一种确保地面用户随时间保持连接的方法。本文还针对适度规模的多无人机群制定了实际的无人机替换问题，并证明它是一个NP难问题，其中最优解具有指数复杂度。在这方面，本文的主要目标是评估启发式方法在不同场景下的适用性。本文提出了基于介数中心性的启发式算法（BETA），这是一种基于图论的启发式算法。BETA不仅能生成接近最优的解决方案（甚至与精确结果有99%的相似度），还能改进两种实际解决方案，尤其是在资源匮乏的场景中。
