  In this paper, we consider a cellular-connected unmanned aerial vehicle (UAV)
with an information collection and transmission mission for multiple ground
targets. Specifically, the UAV is required to collect a fixed amount of
information of each target by hovering at a pre-determined location (via e.g.,
photography/videography/sensing), and transmit all the collected information to
the cellular network during its flight. We aim to jointly optimize the UAV's
trajectory and the information collection order of the ground targets to
minimize the mission completion time. The formulated problem is NP-hard due to
the need of visiting the information collection locations for all targets;
moreover, the UAV's trajectories over different time durations are coupled in
non-convex constraints for ensuring information transmission completion. To
handle this difficult problem, we first propose a structured communication
protocol between the UAV and the cellular network, which decouples the UAV's
trajectory designs in different time durations. Then, under the proposed
protocol, we establish an equivalent graph-based model for the considered
problem, and devise a low-complexity algorithm for finding an approximate
solution by exploiting the problem structure and leveraging graph theory.
Numerical results show that our proposed design achieves efficient information
collection and transmission, and outperforms various benchmark schemes.
