Drones have drawn considerable attention as the agents in wireless data collection for agricultural applications, by virtue of their three-dimensional mobility and dominant line-of-sight communication channels. Existi...
详细信息
Drones have drawn considerable attention as the agents in wireless data collection for agricultural applications, by virtue of their three-dimensional mobility and dominant line-of-sight communication channels. Existing works mainly exploit dedicated drones via deployment and maintenance, which is insufficient regarding resource and cost-efficiency. In contrast, leveraging existing delivery drones for the data collection on their way of delivery, called delivery drones’ piggybacking, is a promising solution. For achieving such cost-efficiency, drone scheduling inevitably stands in front, but the delivery missions involved have escalated it to a wholly different and unexplored problem. As an attempt, we first survey 514 delivery workers and conduct field experiments; noticeably, the collection cost, which mostly comes from the energy consumption of drones’ piggybacking, is determined by the decisions on package-route scheduling and data collection time distribution. Based on such findings, we build a new model that jointly optimizes these two decisions to maximize data collection amount, subject to the collection budget and delivery constraints. Further model analysis finds it a Mixed Integer Non-Linear Programming problem, which is NP-hard. The major challenge stems from interdependence entangling the two decisions. For this point, we propose Delta, a \(\frac{1}{9+\delta }\)-approximation delivery drone scheduling algorithm. The key idea is to devise an approximate collection time distribution scheme leveraging energy slicing, which transforms the complex problem with two interdependent variables into a submodular function maximization problem only with one variable. The theoretical proofs and extensive evaluations verify the effectiveness and the near-optimal performance of Delta.
暂无评论