Heuristic Algorithms for Co-scheduling of Edge Analytics and Routes for UAV Fleet Missions
Heuristic Algorithms for Co-scheduling of Edge Analytics and Routes for UAV Fleet Missions
复制标题
DOI：
10.1109/infocom42981.2021.9488740
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Aakash Khochare;Yogesh L. Simmhan;Francesco Betti Sorbelli;Sajal K. Das
中科院分区：
文献类型：
--
作者：
Aakash Khochare;Yogesh L. Simmhan;Francesco Betti Sorbelli;Sajal K. Das
无人驾驶飞行器（UAV）或无人机越来越多地用于城市应用，如交通监测和建筑勘测。自主导航使无人机能够访问航路点并完成任务中的各项活动。一项常见的活动是使用机载摄像头悬停并观察一个位置。深度神经网络（DNN）的进步使得可以对这类视频进行分析以实现自动决策。无人机还具备边缘计算能力，以便由这类DNN进行机载推理。为此，对于一个无人机群，我们提出了一种新颖的任务调度问题（MSP），它共同调度飞行路线以在航路点访问并录制视频，以及随后的机载边缘分析。所提出的调度方案在满足活动期限以及能量和计算约束的条件下，使活动的效用最大化。我们首先证明MSP是NP难问题，然后通过构建一个混合整数线性规划（MILP）问题来对其进行最优求解。接下来，我们设计了两种高效的启发式算法，jsc和vrc，它们提供快速的次优解。使用真实无人机轨迹对这三种调度器进行评估，展示了在不同工作负载下效用 - 运行时间的权衡。
Unmanned Aerial Vehicles (UAVs) or drones are increasingly used for urban applications like traffic monitoring and construction surveys. Autonomous navigation allows drones to visit waypoints and accomplish activities as part of their mission. A common activity is to hover and observe a location using on-board cameras. Advances in Deep Neural Networks (DNNs) allow such videos to be analyzed for automated decision making. UAVs also host edge computing capability for on-board inferencing by such DNNs. To this end, for a fleet of drones, we propose a novel Mission Scheduling Problem (MSP) that co-schedules the flight routes to visit and record video at waypoints, and their subsequent on-board edge analytics. The proposed schedule maximizes the utility from the activities while meeting activity deadlines as well as energy and computing constraints. We first prove that MSP is NP-hard and then optimally solve it by formulating a mixed integer linear programming (MILP) problem. Next, we design two efficient heuristic algorithms, jsc and vrc, that provide fast sub-optimal solutions. Evaluation of these three schedulers using real drone traces demonstrate utility–runtime trade-offs under diverse workloads.