  Unmanned Aerial Vehicle (UAV) networks have emerged as a promising technique
to rapidly provide wireless coverage to a geographical area, where a flying UAV
can be fast deployed to serve as cell site. Existing work on UAV-enabled
wireless networks overlook the fast UAV deployment for wireless coverage, and
such deployment problems have only been studied recently in sensor networks.
Unlike sensors, UAVs should be deployed to the air and they are generally
different in flying speed, operating altitude and wireless coverage radius. By
considering such UAV heterogeneity to cover the whole target area, this paper
studies two fast UAV deployment problems: one is to minimize the maximum
deployment delay among all UAVs (min-max) for fairness consideration, and the
other is to minimize the total deployment delay (min-sum) for efficiency
consideration. We prove both min-max and min-sum problems are NP-complete in
general. When dispatching UAVs from the same location, we present an optimal
algorithm of low computational complexity $O(n^2)$ for the min-max problem.
When UAVs are dispatched from different locations, we propose to preserve their
location order during deployment and successfully design a fully polynomial
time approximation scheme (FPTAS) of computation complexity $O(n^2 \log
\frac{1}{\epsilon})$ to arbitrarily approach the global optimum with relative
error $\epsilon$. The min-sum problem is more challenging. When UAVs are
dispatched from the same initial location, we present an approximation
algorithm of linear time. As for the general case, we further reformulate it as
a dynamic program and propose a pseudo polynomial-time algorithm to solve it
optimally.
