# A Hybrid Metaheuristic Algorithm for the Efficient Placement of UAVs
## 1 Introduction  
Unmanned Aerial Vehicles (UAV), also known as remotely piloted aircraft, were initially used in military applications. Nevertheless, with the development of various technologies in the telecommunications industry, UAVs have become more affordable and accessible to civilian and commercial applications [1]. This has eased the use and allowed for the application of multiple UAVs in singular tasks, such as traffic control, cargo transport, emergency and rescue operations, weather monitoring, among others. In these tasks, it is expected that UAVs are enabled with communication resources in order to allow the exchange of information with other agents of the environment in a bidirectional way. The use of UAVs in emergency and unexpected circumstances, such as disaster relief and service recovery, has become a focus of study, because the deployment of terrestrial infrastructure is economically infeasible or simply not doable. Compared to a single UAV, there are several advantages to establishing and using a system with multiple UAVs, which can be enumerated as follows [2]: (_i_) the purchase and maintenance of several small incrafts is cheaper than a large UAV with a size equivalent to the group formed by small ones; (_ii_) the use of a large UAV scarcely increases the coverage area, whereas multiple UAVs increase the scalability of the operation easily, and (_iii_) in the event of UAV failure, the possibility of \"survival\" or continuity in the execution of a multi-UAV mission is much greater than in a mission in which the failing UAV is the only executor. Naturally, the deployment of an aerial networking infrastructure formed by multiple UAVs also brings about a number of challenges and potential disadvantages if compared to the use of a single UAV. In particular, aerial multi-hop communication introduces additional delays to packet flows due to a number of factors, such as (_i_) the typical store-and-forward operation of UAVs when relaying packets to each other; (_ii_) themechanisms of the medium access control (MAC) protocol in place to share the wireless channel(s) and support reliable data transfer; (_iii_) packet buffering in all UAVs; and, (_iv_) distributed user association, authentication procedures, etc. Needless to say, other issues arise that are related to trust and security of many deployed UAVs [3; 4]. In this work, we look at the problem of UAV-assisted wireless communications [5], where UAVs are deployed to establish an aerial communication platform to provide wireless access for terrestrial users from the sky. In other words, the deployed UAVs do not generate their own data packets. Instead, the UAVs simply serve as aerial relays to connect users on the ground. We consider that each station is assigned to a single UAV, which is responsible for carrying data traffic to or from users assigned to other UAVs. Hence, different from recent work in the literature, where the UAV placement problem seeks to maximize the number of covered users [6; 7] or to minimize the number of required UAVs [8; 9], our goal is to maximize the total (sum) link capacity of the aerial communication infrastructure (considering both air-to-ground (A2G) and air-to-air (A2A) link capacities) given a fixed number of UAVs that are placed at the same (given) altitude from the ground. For that, and in line with other works [6; 7; 8; 9; 10; 11], perfect user location information (ULI) is assumed. Because of such constraints, there is no minimum link rate requirement in our problem, and the provisioning of connectivity to all users is of paramount importance. In this sense, the solution we provide is best suited to application scenarios related to disaster relief, rescue operations, and provisioning of user connectivity in remote or hostile environments, for example.