# UAV Charging Station Placement in Opportunistic Networks
## 1 Introduction  
Unmanned aerial vehicles (UAV)s, also known as drones, are aircraft that can fly autonomously or as interconnected swarms to perform various tasks, such as data collection and delivery. Although UAVs have been used by the military for many years to fulfill a multitude of mission profiles across surveillance, rescue, border observation, firefighting, etc., they are now commercially available, with prices ranging from hundreds of dollars for small short-range drones to professional sensor-powered drones that cost thousands of dollars. As UAVs have gained popularity, their use has spread to a wide variety of civilian applications, such as traffic monitoring [1, 2], public safety [3], emergency communications [4], and many others [5, 6, 7, 8]. Recently, companies such as Amazon, UPS, and Google are adding drones to their vehicle fleet to make delivery services to customers much faster [9, 10]. We expect that this broad appeal, derived from UAVs characteristics of mobility and flexibility, will increase our contact with UAVs in our daily lives. One challenge to the increased civilian usage of UAVs is that of limited battery life. Civilian UAVs are generally smaller than military variants with lower charge capacities, restricting cruise times to approximately 30 min and, thus, resulting in more frequent recharge cycles. To address this challenge, the application scenario we will consider is a UAV-aided opportunistic network. In a UAV-aided opportunistic network, the UAVs cruise around an area and communicate with both mobile nodes on the ground and other UAVs in a peer-to-peer manner, as shown in Figure 1. As the routes between the mobile nodes are created dynamically via the passing UAVs overhead, messages created by the mobile nodes are distributed by the UAVs using the store-carry-and-forward paradigm. In this model each node will store a received message and forward it along to newly discovered nodes who continue the pattern until the ultimate recipient is encountered. The integrationof UAVs in this type of network can provide various benefits, however, the UAVs' limited on-board battery life restricts their flight time. An efficient charging strategy can help achieve maximum productivity of the UAVs. One such challenge that UAVs have been applied to is map scanning. Although few studies used one UAV for scanning the entire map [11; 12; 13], scanning the whole map with a single UAV may not always be possible or practical, as the flight time is relatively short for commercially available UAVs. To resolve this issue, a scanning method to cluster the map into small sections should be developed along with an approach to maximize the flight time of the UAVs through the strategic placement of charging stations. The locations of these stations are critically important as the UAVs need to keep reasonable proximity to a charging station so they can return whenever they drain their batteries. Charging stations that are too close together may affect the UAVs' ability to scan different parts on the map while stations that are too far away from each other may cause fragmented areas to appear on the map. Another challenge that arises, due to the nature of the opportunistic network environment, is the selection of an appropriate packet routing strategy. Routing is the decision-making process in which a given node selects one or more of its outgoing links to forward a packet on its journey to the final destination. The routing mechanism is responsible for choosing appropriate paths to transfer data based on network requirements and restrictions. In addition to providing a route to the destination, many of the existing routing protocols also aim to optimize various metrics, such as minimizing energy consumption, congestion, storage, maintenance, etc. [14; 15; 16; 17]. As the topology of opportunistic networks is dynamic lacking fixed end-to-end transmission routes between nodes, traditional topology-based routing algorithms cannot be directly applied.