  The adoption of UAVs in communication networks is becoming reality thanks to
the deployment of advanced solutions for connecting UAVs and using them as
communication relays. However, the use of UAVs introduces novel energy
constraints and scheduling challenges in the dynamic management of network
devices, due to the need to call back and recharge, or substitute, UAVs that
run out of energy. In this paper, we design UAV recharging schemes under
realistic assumptions on limited flight times and time consuming charging
operations. Such schemes are designed to minimize the size of the fleet to be
devoted to a persistent service of a set of aerial locations, hence its cost.
We consider a fleet of homogeneous UAVs both under homogeneous and
heterogeneous service topologies. For UAVs serving aerial locations with
homogeneous distances to a recharge station, we design a simple scheduling,
that we name HORR, which we prove to be feasible and optimal, in the sense that
it uses the minimum possible number of UAVs to guarantee the coverage of the
aerial service locations. For the case of non-evenly distributed aerial
locations, we demonstrate that the problem becomes NP-hard, and design a
lightweight recharging scheduling scheme, PHERR, that extends the operation of
HORR to the heterogeneous case, leveraging the partitioning of the set of
service locations. We show that PHERR is near-optimal because it approaches the
performance limits identified through a lower bound that we formulate on the
total fleet size.
