Optimizing Connectivity and Coverage for UAV Paths Toward BVLoS Operations

UAVs, commonly known as drones, are increasingly used in various civilian applications. However, strict aviation regulations currently restrict their operation to the Visual Line of Sight (VLoS) of the operator, limiting their range due to safety concerns. To unlock their full potential, significant efforts are underway to enable Beyond Visual Line of Sight (BVLoS) operations, allowing flights to be remotely supervised from takeoff to landing. This paper presents a viable BVLoS solution that ensures full flight coverage and continuous connectivity with the flight observer by leveraging existing ground infrastructure. Precisely, the proposed approach aims to minimize the number of hops (eccentricity) between the flight observer and the drone while ensuring the coverage of the drone trajectory with at least one or multiple antennas. Or, to minimize the antennas used for the coverage while also reducing eccentricity. We first address single-trajectory problems, which can be solved in polynomial time, and then extend our focus to multi-trajectory problems, which are computationally intractable. Finally, we evaluate the performance of our algorithms using randomly generated instances across various ground network topologies, including random geometric graphs and regular grids.