  Modern wireless traffic demand pushes Internet Service Providers to develop
effective strategies to improve user experience. Since deploying dense Base
Stations (BSs) is not cost efficient, an alternative is to deploy autonomous
drones to supplement existing BSs. A street graph is adopted to represent the
area of interest. The outdoor User Equipments (UEs) to be served locate near
streets and the 2D projections of drones are restricted to streets to avoid
collision with buildings. We build up a UE density function based on a real
dataset, reflecting the traffic in the area. We study four problems: where to
deploy single drone to cover maximum UEs, where to deploy $k$ drones cover
maximum UEs subject to an inner drone distance constraint, where to deploy $k$
drones cover maximum UEs subject to inner drone distance constraint and drones'
battery constraints, and the minimum drones to cover a given percentage of UEs
subject to inner drone distance constraint. We prove that the latter three
problems are NP-hard and propose greedy algorithms with theoretical analysis.
To our best knowledge, this is the first paper to consider the battery
constraints for drone deployments. Extensive simulations have been conducted to
verify the effectiveness of our approaches.
