Placement of unmanned aerial vehicles as communication relays in two-Tiered multi-Agent system: Clustering based methods

The network performance and the unmanned aerial vehicle (UAV) number are important objectives when UAVs are placed as communication relays to enhance the multi-Agent information exchange. The problem is a non-deterministic polynomial hard (NP-hard) multi-objective optimization problem, instead of generating a Pareto solution, this work focuses on considering both objectives at the same level so as to achieve a balanced solution between them. Based on the property that agents connected to the same UAV are a cluster, two clustering-based algorithms, M-K-means (MKM) and modified fast search and find density of peaks (MFSFDP) methods, are first proposed. Since the former algorithm requires too much computational time and the latter one requires too many relays, an algorithm for the balanced network performance and relay number (BPN) is proposed by discretizing the area to avoid missing the optimal relay positions and defining a new local density function to reflect the network performance metric. Simulation results demonstrate that the proposed algorithms are feasible and effective. Comparisons between these algorithms show that the BPN algorithm uses fewer relay UAVs than the MFSFDP and classic set-covering based algorithm, and its computational time is far less than the MKM algorithm.