# OADC: An Obstacle-Avoidance Data Collection Scheme Using Multiple Unmanned Aerial Vehicles
## 1 Introduction  
Wireless sensor networks (WSNs), combined with the IoT, are being widely used in numerous applications, such as smart grids, home and industry automation, landslide detection, and military operations [1, 2, 3]. In these applications, a sink is usually installed to collect the data from the sensor node, which usually forwards the data to the sink in a multiple-hop fashion. However, multi-hop transmission is not always practical because there may be no infrastructure to install the sink or gateway in remote places or in emergencies. In addition, forwarding data via the multi-hop method results in an energy-hole problem; it decreases the network's lifetime, as relay nodes near the sink run out of battery faster than other nodes, and it increases the data transmission delay [4, 5]. Therefore, unmanned aerial vehicle (UAV)-aided WSNs have been proposed in recent years. UAVs collect data from the sensors and send them to the base stations [2, 6, 7]. On the other hand, collecting data using UAVs is challenging because UAVs need to visit the sensors to collect the data. Different visiting orders or UAV trajectories lead to different total traveling distances and data transmission times. Several studies have examined UAV trajectory or path planning in UAV-aided data collection in WSNs [8, 9, 10, 11, 2, 12, 13, 14, 15]. However, these studies did not consider the existence of obstacles in the paths of UAVs, whereas there can be many obstacles (e.g., buildings, mountains, big trees, and no-fly zone areas) in a UAV's trajectory that need to be avoided when it flies from one sensor to another. Although some studies considered obstacles in the UAV trajectories [16, 17, 18, 19, 20, 21], they did not consider the UAV path as the Hamiltonian path, which is impractical because UAVs arebattery-constrained devices and need to return to the base station (BS) to recharge their batteries after a given period of data collection. Therefore, this paper proposes an obstacle-avoidance data-collection (OADC) scheme, where multiple UAVs collect data from a group of sensors deployed in an obstacle-constrained environment. Each UAV flies to the sensors assigned to it only once and collects the data before returning to the BS to deliver the data, which is a Hamiltonian cycle. If there is an obstacle between any two sensors, UAVs must take a detour by visiting some borderline points around the obstacles; otherwise, they can directly visit the next sensor on the path. The borderline points are the points around an obstacle where UAVs can fly to make a detour. Note that the Hamiltonian graph in this paper only considers sensors as vertices. In addition, the flight time is also considered because UAVs are battery-constrained and can only fly for a given amount of time. The considered problem is formulated as an integer linear programming problem (ILP) problem which is NP-hard, and hence it is very challenging to solve. Therefore, to address the problem, we first designed a detour-points-selection algorithm, namely, the vector-rotation angle-based obstacle avoidance algorithm (VRAOA), which selects points for detouring from the borderline points of an obstacle by making a convex polygon with the shortest traveling distance (which has the shortest traveling distance if a tour starts from a borderline point of an obstacle and returns to that borderline point after covering the whole obstacle). The VRAOA algorithm is applied to each obstacle in the environment. Then, a genetic-algorithm-based obstacle-aware path planning scheme for UAVs called the genetic algorithm (GA) with VRAOA (GA w/VRAOA) is proposed, where VRAOA, along with the Dijkstra algorithm, finds a detour path between any two sensors when there is an obstacle. The performance of GA w/VRAOA is validated by conducting simulations with various parameter values.