Energy-efficient trajectory planning for a multi-UAV-assisted mobile edge computing system

Pei-qiu HUANG; Yong WANG; Ke-zhi WANG

doi:10.1631/FITEE.2000315

Your Location：

Home >

Browse articles >

Energy-efficient trajectory planning for a multi-UAV-assisted mobile edge computing system

Special Feature on Cooperative Multi-UAV Systems | Updated：2022-05-19

- Energy-efficient trajectory planning for a multi-UAV-assisted mobile edge computing system
- 多无人机辅助移动边缘计算系统能量有效的轨迹规划
- Frontiers of Information Technology & Electronic Engineering Vol. 21, Issue 12, Pages: 1713-1725(2020)
- Affiliations：
  
  School of Automation, Central South University, Changsha 410083, China
  Department of Computer and Information Sciences, Northumbria University, Newcastle NE1 8ST, UK
- Author bio：
  
  [ "HUANG Pei-qiu, E-mail: pqhuang@csu.edu.cn" ]
  WANG Yong, E-mail: ywang@csu.edu.cn
  [ "WANG Ke-zhi, E-mail: kezhi.wang@northumbria.ac.uk" ]
- Funds：
- DOI：10.1631/FITEE.2000315
  CLC： TN929.5;TP301.6
- Received：02 July 2020，
  
  Revised：2020-10-29，
  
  Published：2020-12
- Accepted：
Scan QR Code
Pei-qiu HUANG, Yong WANG, Ke-zhi WANG. Energy-efficient trajectory planning for a multi-UAV-assisted mobile edge computing system[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(12): 1713-1725.
DOI：

Pei-qiu HUANG, Yong WANG, Ke-zhi WANG. Energy-efficient trajectory planning for a multi-UAV-assisted mobile edge computing system[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(12): 1713-1725. DOI： 10.1631/FITEE.2000315.

摘要

本文研究多无人机辅助移动边缘计算系统，该系统中无人机可作为边缘服务器为物联网设备提供计算服务。本文目标是通过规划无人机轨迹将系统能耗最小化。规划无人机轨迹不仅要考虑停靠点的访问顺序，还要考虑停靠点的布局（包括其数量和位置）以及无人机与停靠点的关联。为解决该问题，提出一个3阶段的能量有效轨迹规划算法。第一阶段采用种群大小可变的差分进化算法，同时更新停靠点的数量和位置。第二阶段采用

均值聚类算法将给定停靠点聚类为一系列子组，其中子组数目等于无人机数目，且每个子组中包含一个无人机需要访问的所有停靠点。第三阶段提出一种低复杂度的贪婪方法用于快速获取每个子组中停靠点的访问顺序。最后，在一组不同规模的实例上验证所提出算法的有效性。

Abstract

We study a mobile edge computing system assisted by multiple unmanned aerial vehicles (UAVs)

where the UAVs act as edge servers to provide computing services for Internet of Things devices. Our goal is to minimize the energy consumption of this system by planning the trajectories of UAVs. This problem is difficult to address because when planning the trajectories

we need to consider not only the order of stop points (SPs)

but also their deployment (including the number and locations) and the association between UAVs and SPs. To tackle this problem

we present an energy-efficient trajectory planning algorithm (TPA) which comprises three phases. In the first phase

a differential evolution algorithm with a variable population size is adopted to update the number and locations of SPs at the same time. In the second phase

the

-means clustering algorithm is employed to group the given SPs into a set of clusters

where the number of clusters is equal to that of UAVs and each cluster contains all SPs visited by the same UAV. In the third phase

to quickly generate the trajectories of UAVs

we propose a low-complexity greedy method to construct the order of SPs in each cluster. Compared with other algorithms

the effectiveness of TPA is verified on a set of instances at different scales.

关键词

Keywords

references

TM Chan , , , KF Man , , , KS Tang , , , 等 . . A jumping-genes paradigm for optimizing factory WLAN network . . IEEE Trans Ind Inform , , 2007 . . 3 ( ( 1 ): ): 33 - - 43 . . DOI: 10.1109/TII.2006.890528 http://doi.org/10.1109/TII.2006.890528 . .

J Chen , , , X Zhang , , , B Xin , , , 等 . . Coordination between unmanned aerial and ground vehicles: a taxonomy and optimization perspective . . IEEE Trans Cybern , , 2016 . . 46 ( ( 4 ): ): 959 - - 972 . . DOI: 10.1109/TCYB.2015.2418337 http://doi.org/10.1109/TCYB.2015.2418337 . .

WH Chen , , , BC Liu , , , HW Huang , , , 等 . . When UAV swarm meets edge-cloud computing: the QoS perspective . . IEEE Netw , , 2019 . . 33 ( ( 2 ): ): 36 - - 43 . . DOI: 10.1109/MNET.2019.1800222 http://doi.org/10.1109/MNET.2019.1800222 . .

XH Diao , , , JC Zheng , , , YM Cai , , , 等 . . Fair data allocation and trajectory optimization for UAV-assisted mobile edge computing . . IEEE Commun Lett , , 2019 . . 23 ( ( 12 ): ): 2357 - - 2361 . . DOI: 10.1109/LCOMM.2019.2943461 http://doi.org/10.1109/LCOMM.2019.2943461 . .

Y Du , , , K Yang , , , KZ Wang , , , 等 . . Joint resources and workflow scheduling in UAV-enabled wirelessly-powered MEC for IoT systems . . IEEE Trans Veh Technol , , 2019 . . 68 ( ( 10 ): ): 10187 - - 10200 . . DOI: 10.1109/TVT.2019.2935877 http://doi.org/10.1109/TVT.2019.2935877 . .

S Garg , , , A Singh , , , S Batra , , , 等 . . UAV-empowered edge computing environment for cyber-threat detection in smart vehicles . . IEEE Netw , , 2018 . . 32 ( ( 3 ): ): 42 - - 51 . . DOI: 10.1109/MNET.2018.1700286 http://doi.org/10.1109/MNET.2018.1700286 . .

XY Hu , , , KK Wong , , , K Yang , , , 等 . . UAV-assisted relaying and edge computing: scheduling and trajectory optimization . . IEEE Trans Wirel Commun , , 2019 . . 18 ( ( 10 ): ): 4738 - - 4752 . . DOI: 10.1109/TWC.2019.2928539 http://doi.org/10.1109/TWC.2019.2928539 . .

L Huang , , , GC Wang , , , T Bai , , , 等 . . An improved fruit fly optimization algorithm for solving traveling salesman problem . . Front Inform Technol Electron Eng , , 2017 . . 18 ( ( 10 ): ): 1525 - - 1533 . . DOI: 10.1631/FITEE.1601364 http://doi.org/10.1631/FITEE.1601364 . .

PQ Huang , , , Y Wang , , , KZ Wang , , , 等 . . A bilevel optimization approach for joint offloading decision and resource allocation in cooperative mobile edge computing . . IEEE Trans Cybern , , 2020a . . 50 ( ( 10 ): ): 4228 - - 4241 . . DOI: 10.1109/TCYB.2019.2916728 http://doi.org/10.1109/TCYB.2019.2916728 . .

PQ Huang , , , Y Wang , , , KZ Wang , , , 等 . . Differential evolution with a variable population size for deployment optimization in a UAV-assisted IoT data collection system . . IEEE Trans Emerg Top Comput Intell , , 2020b . . 4 ( ( 3 ): ): 324 - - 335 . . DOI: 10.1109/TETCI.2019.2939373 http://doi.org/10.1109/TETCI.2019.2939373 . .

AK Jain . . Data clustering: 50 years beyond K -means . . Patt Recogn Lett , , 2010 . . 31 ( ( 8 ): ): 651 - - 666 . . DOI: 10.1016/j.patrec.2009.09.011 http://doi.org/10.1016/j.patrec.2009.09.011 . .

S Jeong , , , O Simeone , , , J Kang . . Mobile edge computing via a UAV-mounted cloudlet: optimization of bit allocation and path planning . . IEEE Trans Veh Technol , , 2018 . . 67 ( ( 3 ): ): 2049 - - 2063 . . DOI: 10.1109/TVT.2017.2706308 http://doi.org/10.1109/TVT.2017.2706308 . .

MS Jin , , , S Gao , , , HB Luo , , , 等 . . Cost-effective resource segmentation in hierarchical mobile edge clouds . . Front Inform Technol Electron Eng , , 2019 . . 20 ( ( 9 ): ): 1209 - - 1220 . . DOI: 10.1631/FITEE.1800203 http://doi.org/10.1631/FITEE.1800203 . .

MS Li , , , N Cheng , , , J Gao , , , 等 . . Energy-efficient UAV-assisted mobile edge computing: resource allocation and trajectory optimization . . IEEE Trans Veh Technol , , 2020 . . 69 ( ( 3 ): ): 3424 - - 3438 . . DOI: 10.1109/TVT.2020.2968343 http://doi.org/10.1109/TVT.2020.2968343 . .

JE Low , , , D Sufiyan , , , LST Win , , , 等 . . Design of a hybrid aerial robot with multi-mode structural efficiency and optimized mid-air transition . . Unmann Syst , , 2019 . . 7 ( ( 4 ): ): 195 - - 213 . . DOI: 10.1142/S2301385019500067 http://doi.org/10.1142/S2301385019500067 . .

M Mozaffari , , , W Saad , , , M Bennis , , , 等 . . A tutorial on UAVs for wireless networks: applications, challenges, and open problems . . IEEE Commun Surv Tutor , , 2019 . . 21 ( ( 3 ): ): 2334 - - 2360 . . DOI: 10.1109/COMST.2019.2902862 http://doi.org/10.1109/COMST.2019.2902862 . .

M Ryerkerk , , , R Averill , , , K Deb , , , 等 . . A survey of evolutionary algorithms using metameric representations . . Genet Program Evol Mach , , 2019 . . 20 ( ( 4 ): ): 441 - - 478 . . DOI: 10.1007/s10710-019-09356-2 http://doi.org/10.1007/s10710-019-09356-2 . .

R Storn , , , K Price . . Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces . . J Glob Optim , , 1997 . . 11 ( ( 4 ): ): 341 - - 359 . . DOI: 10.1023/A:1008202821328 http://doi.org/10.1023/A:1008202821328 . .

CK Ting , , , CN Lee , , , HC Chang , , , 等 . . Wireless heterogeneous transmitter placement using multiobjective variable-length genetic algorithm . . IEEE Trans Syst Man Cybern Part B (Cybern) , , 2009 . . 39 ( ( 4 ): ): 945 - - 958 . . DOI: 10.1109/TSMCB.2008.2010951 http://doi.org/10.1109/TSMCB.2008.2010951 . .

BC Wang , , , HX Li , , , QF Zhang , , , 等 . . Decomposition-based multiobjective optimization for constrained evolutionary optimization . . IEEE Trans Syst Man Cybern Syst, in press , , 2018 . . DOI: 10.1109/TSMC.2018.2876335 http://doi.org/10.1109/TSMC.2018.2876335 . .

JH Wang , , , Y Zhou , , , Y Wang , , , 等 . . Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: formulation, instances, and algorithms . . IEEE Trans Cybern , , 2016 . . 46 ( ( 3 ): ): 582 - - 594 . . DOI: 10.1109/TCYB.2015.2409837 http://doi.org/10.1109/TCYB.2015.2409837 . .

KZ Wang , , , PQ Huang , , , K Yang , , , 等 . . Unified offloading decision making and resource allocation in ME-RAN . . IEEE Trans Veh Technol , , 2019 . . 68 ( ( 8 ): ): 8159 - - 8172 . . DOI: 10.1109/TVT.2019.2926513 http://doi.org/10.1109/TVT.2019.2926513 . .

L Wang , , , PQ Huang , , , KZ Wang , , , 等 . . RL-based user association and resource allocation for multi-UAV enabled MEC . . Proc 15$.{\rm th}$ Int Wireless Communications & Mobile Computing Conf , , 2019 . . p.741 - - 746 . . DOI: 10.1109/IWCMC.2019.8766458 http://doi.org/10.1109/IWCMC.2019.8766458 . .

Y Wang , , , ZX Cai , , , QF Zhang . . Differential evolution with composite trial vector generation strategies and control parameters . . IEEE Trans Evol Comput , , 2011 . . 15 ( ( 1 ): ): 55 - - 66 . . DOI: 10.1109/TEVC.2010.2087271 http://doi.org/10.1109/TEVC.2010.2087271 . .

Y Wang , , , H Liu , , , H Long , , , 等 . . Differential evolution with a new encoding mechanism for optimizing wind farm layout . . IEEE Trans Ind Inform , , 2018 . . 14 ( ( 3 ): ): 1040 - - 1054 . . DOI: 10.1109/TII.2017.2743761 http://doi.org/10.1109/TII.2017.2743761 . .

Y Wang , , , ZY Ru , , , KZ Wang , , , 等 . . Joint deployment and task scheduling optimization for large-scale mobile users in multi-UAV-enabled mobile edge computing . . IEEE Trans Cybern , , 2020 . . 50 ( ( 9 ): ): 3984 - - 3997 . . DOI: 10.1109/TCYB.2019.2935466 http://doi.org/10.1109/TCYB.2019.2935466 . .

B Xin , , , J Chen , , , J Zhang , , , 等 . . Hybridizing differential evolution and particle swarm optimization to design powerful optimizers: a review and taxonomy . . IEEE Trans Syst Man Cybern Part C (Appl Rev) , , 2012 . . 42 ( ( 5 ): ): 744 - - 767 . . DOI: 10.1109/TSMCC.2011.2160941 http://doi.org/10.1109/TSMCC.2011.2160941 . .

JW Xu , , , K Ota , , , MX Dong , , , 等 . . SIoTFog: Byzantine-resilient IoT fog networking . . Front Inform Technol Electron Eng , , 2018 . . 19 ( ( 12 ): ): 1546 - - 1557 . . DOI: 10.1631/FITEE.1800519 http://doi.org/10.1631/FITEE.1800519 . .

ZH Yang , , , CH Pan , , , KZ Wang , , , 等 . . Energy efficient resource allocation in UAV-enabled mobile edge computing networks . . IEEE Trans Wirel Commun , , 2019 . . 18 ( ( 9 ): ): 4576 - - 4589 . . DOI: 10.1109/TWC.2019.2927313 http://doi.org/10.1109/TWC.2019.2927313 . .

AH Zaini , , , LH Xie . . Distributed drone traffic coordination using triggered communication . . Unmann Syst , , 2020 . . 8 ( ( 1 ): ): 1 - - 20 . . DOI: 10.1142/S2301385020500016 http://doi.org/10.1142/S2301385020500016 . .

J Zhang , , , T Huang , , , S Wang , , , 等 . . Future Internet: trends and challenges . . Front Inform Technol Electron Eng , , 2019 . . 20 ( ( 9 ): ): 1185 - - 1194 . . DOI: 10.1631/FITEE.1800445 http://doi.org/10.1631/FITEE.1800445 . .

J Zhang , , , L Zhou , , , FH Zhou , , , 等 . . Computation-efficient offloading and trajectory scheduling for multi-UAV assisted mobile edge computing . . IEEE Trans Veh Technol , , 2020 . . 69 ( ( 2 ): ): 2114 - - 2125 . . DOI: 10.1109/TVT.2019.2960103 http://doi.org/10.1109/TVT.2019.2960103 . .

L Zhang , , , Z Zhao , , , QW Wu , , , 等 . . Energy-aware dynamic resource allocation in UAV assisted mobile edge computing over social Internet of vehicles . . IEEE Access , , 2018 . . 6 56700 - - 56715 . . DOI: 10.1109/ACCESS.2018.2872753 http://doi.org/10.1109/ACCESS.2018.2872753 . .

MD Zollars , , , RG Cobb , , , DJ Grymin . . Optimal SUAS path planning in three-dimensional constrained environments . . Unmann Syst , , 2019 . . 7 ( ( 2 ): ): 105 - - 118 . . DOI: 10.1142/S2301385019500031 http://doi.org/10.1142/S2301385019500031 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Federated deep reinforcement learning based computation offloading in a low Earth orbit satellite edge computing system

A survey of energy-efficient strategies for federated learning in mobile edge computing

A double-layered nonlinear model predictive control based control algorithm for local trajectory planning for automated trucks under uncertain road adhesion coefficient conditions

Consensus-based three-dimensional multi-UAV formation control strategy with high precision

Intelligent computing budget allocation for on-road trajectory planning based on candidate curves

Related Author

Qing GUO

Xinyu WANG

Jian WU

Min JIA

Panlong YANG

Chunsheng LIU

Tao WU

Nina SHU

Related Institution

School of Electronics and Information Engineering, Harbin Institute of Technology

School of Electronic Engineering, National University of Defense Technology

Department of Computing, Hong Kong Polytechnic University

School of Computer Science and Technology, University of Science and Technology of China

College of Mechanical and Automotive Engineering, Shanghai University of Engineering Science

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰